In this chapter we shall solve how to get maximum coin in a game problem with help of DP.

Problem Statement:

**You and your friend are playing a game to pick numbers from an array of even length. You need to find a solution so that you can pick the maximum sum and you win the game.**

Example array

You are player P1 and your friend is player P2.

Initially you pick 1

Your friend picks 2

You pick 1

Your friend picks 4

Your total = 2

Your friend total = 6

So here you need to come up with a strategy where you will be the winner. We can solve this by DP.

Consider the array:

Initially below will be our DP array:

As we have 4 elements, we took 4 x 4 matrix. Let’s start filling the matrix. We shall get the result at [0,3] index.

As there are 2 players, we indicate like [4, 5]. Here the player 1 will have profit 4 and player 5 will have profit 5. It means, player 1 profit will be the 1^{st} element, and player 2 profit will be the 2^{nd} element.

So initially we have only 1 element i.e. 4 and its index is 0.

So if you have only ‘4’, you will choose ‘4’ player 2 will choose 0. As there is only 1 element, and player 1 has chosen it, player 2 will get 0. Hence we can fill our DP array as dp[0,0] = [4,0].

Similarly, if you have only 8 dp[1, 1] =[8, 0]

Similarly, if you have only 1 dp[2, 2] =[1, 0]

Similarly, if you have only 2 dp[3, 3] =[2, 0]

The updated DP table will be

Now let’s take 2 elements at t time and compute the same.

First you have [4, 8]. Hence player P1 will pick 8 and player 2 will pick 4. Hence dp[0, 1] = [8, 4].

Next you have [8, 1]. Here P1 = 8, P2 =1.

Hence dp[1, 2] = [8, 1].

Next you have [1, 2]. Here P1 = 2, P2 =1.

Hence dp[2, 3] = [2, 1].

Hence our final DP array will be:

From the above can we derive a DP formula? Yes, we can derive.

Ok, Concentrate below:

For the index dp[0, 1], we have the elements [4, 8]. If the player P1, choose 4, then player P2 choose 8, then again player P1 will have to choose what’s left after player P2 has chosen.

Initially P1 chose 4m P2 chose 8. As the player P2 has chose 8 and it’s index is 1, you need to check the 2^{nd}value in dp[1, 1]. The 2^{nd} value i.e. P2’s value is 0. You add the value that you have selected i.e 4 + 0= 4.

Again if you choose 8 in [4, 8], P2 will choose 4. You need to check the 2^{nd} value for the index [0, 0] i.e 0. You add to the value you have selected i.e 8 + 0 = 8. Now you have 2 values [4, 8]. You need to take the max of the value i.e. 8. Hence we get [8, 4].

Next, we shall select 3 elements [4, 8, 1] and index are [0, 1, 2] and solve with the same approach as above.

So first P1 picks 4, then we need to add with the 2^{nd} value at the index [1,2] ie 4 + 1 = 5.

else P1 picks 1, then we need to add with 2^{nd} value at the index [0, 1] i.e 1 + 4 = 5. In any case, we choose 5.

and P2 will choose 8. Hence for dp[0, 2] = [5, 8]

Now we shall select [8, 1, 2]

If P1 chose 8, we need to add with 2^{nd} value of [2, 3].

8 + 1 = 9

If P1 chose 2, we need to add with 2^{nd} value of [1, 2].

2 + 1 = 3

As max of [9, 3] is 9. P1 will chose 9. P2 will take the next value that we have chosen. i.e P2 will take 1.

Hence dp[1, 3] = [9, 1].

Now we shall take 4 elements at a time.

[4, 8, 1, 2] and index are [0, 1, 2, 3].

If P1 chose 4 then we need to add with 2^{nd} element at the index [1, 3].

i.e 4 + 1 = 5.

If P1 chose 2 then we need to add with 2^{nd} element at the index [0, 2].

i.e 2 + 8 = 10.

We shall choose 10 as it is max and 2^{nd} player gets 4 + 1 = 5.

Hence final dp[0, 3] = [10, 5].

Hence the result.

## Solution in C++

#include <iostream> using namespace std; int get_max_coin(int* arr, int n) { int dp_table[n][n]; for (int gap = 0; gap < n; ++gap) { for (int i = 0, j = gap; j < n; ++i, ++j) { int x = 0; if(((i + 2) <= j)) { x = dp_table[i + 2][j]; } int y = 0; if((i + 1) <= (j - 1)) { y = dp_table[i + 1][j - 1]; } int z = 0; if((i <= (j - 2))) { z = dp_table[i][j - 2]; } dp_table[i][j] = max( arr[i] + min(x, y), arr[j] + min(y, z)); } } return dp_table[0][n - 1]; } int main() { int arr1[] = { 4, 8, 1, 2}; int n = sizeof(arr1) / sizeof(arr1[0]); cout<<"Ans : " <<get_max_coin(arr1, n)<<endl; return 0; }