The greedy coins game Dynamic Programming

The greedy coins game Dynamic Programming Solution :

Question statement There is a row of 2n coins on the table; each coin can have any positive integer value. Two players alternate turns.

On a player’s turn he/she must take one of the two coins on either END of the row of remaining coins, so with each turn the row gets shorter by one.

After all the coins have been taken, the player with the higher total value is the winner.
Decide Strategy and Determine the maximum possible amount of money we can definitely win if we move first.

Let’s look at an example. Suppose the coins start out like this:

3      5      1      2

The first player (let’s call her Alice) can choose either the 3 or the 2. Let’s say she takes the 3. (3 is bigger than 2, right?) Now the table looks like this:

5      1      2

The Second Player’s turn(lets call him Bob) is now allowed to take either the 5 or the 2. His best move is clearly to take the 5, since it’s even bigger than the other two remaining coins combined. After that the table looks like this:

1      2

Alice Will take 2 and Bob will take 1, Who will win ?
Alice has 3 + 2 = 5 and Bob has 5 + 1 = 6.
Though Alice had first chance why she lost ? as she choose Greedy Approach.

Let see this scenario 

3      5      1      2

Alice choose 2 , so Remaining is

3      5      1

Bob has to choose between 3 & 1, so he has to choose 3, Remaining is

5      1

So Alice can now choose 5 and Win with 5+2=7 and Bob will lose with 3+1=4 coins.

Can you try same for Below Coins?

1      3      17      5      9      8

Coding solution.

Lets see how you thought ??

1. The user(alice) chooses the ith coin with value Vi: The opponent(bob) either chooses (i+1)th coin or jth coin.
2. The user chooses the jth coin with value Vj: The opponent either chooses ith coin or (j-1)th coin.

In 1st Choice : The opponent(Bob) intends to choose the coin which leaves the user(alice) with minimum value. i.e. The user can collect the value Vi + min( F(i+2, j), F(i+1, j-1)  )

In 2nd Choice : The opponent intends to choose the coin which leaves the user with minimum value.
i.e. The user can collect the value Vj + min( F(i+1, j-1), F(i, j-2) )

Following is recursive solution that is based on above two choices. We take the maximum of two choices.

F(i, j)  represents the maximum value the user can collect from 
         i'th coin to j'th coin.

    F(i, j)  = Max(Vi + min(F(i+2, j), F(i+1, j-1) ), 
                   Vj + min(F(i+1, j-1), F(i, j-2) )) 
Base Cases
    F(i, j)  = Vi           If j == i
    F(i, j)  = max(Vi, Vj)  If j == i+1

Recursive Solution

#include 
#include 

int max(int a, int b) { return a > b ? a : b; }
int min(int a, int b) { return a < b ? a : b; }

int coinGame(int* arr, int n, int i, int j)
{
    if(i == j)
        return arr[i];
    if( j == i+1)
        return max(arr[i],arr[j]);
        
    return max(arr[i] + min(coinGame(arr,n,i+2, j), coinGame(arr,n,i+1, j-1) ), 
                   arr[j] + min(coinGame(arr,n,i+1, j-1), coinGame(arr,n,i, j-2) )); 

}

int main()
{
	int arr1[] = {8, 15, 3, 7};
	int n = sizeof(arr1)/sizeof(arr1[0]);
	printf("%d\n", coinGame(arr1, n,0,n-1));

	int arr2[] = {2, 2, 2, 2};
	n = sizeof(arr2)/sizeof(arr2[0]);
	printf("%d\n", coinGame(arr2, n,0,n-1));

	int arr3[] = {20, 30, 2, 2, 2, 10};
	n = sizeof(arr3)/sizeof(arr3[0]);
	printf("%d\n", coinGame(arr3, n,0,n-1));

	return 0;
}

Now as you know From this question How to think and create solution in Dynamic Programming

this question greedy coins game can be converted in Dynamic Programming based solution.

Lets covert it.

#include <stdio.h>
#include <limits.h>

int max(int a, int b) { return a > b ? a : b; }
int min(int a, int b) { return a < b ? a : b; }

int coinGameDP(int* arr, int n)
{
	int table[n][n], gap, i, j, x, y, z;

	for (gap = 0; gap < n; ++gap)
	{
		for (i = 0, j = gap; j < n; ++i, ++j)
		{
			x = ((i+2) <= j) ? table[i+2][j] : 0;
			y = ((i+1) <= (j-1)) ? table[i+1][j-1] : 0;
			z = (i <= (j-2))? table[i][j-2]: 0;

			table[i][j] = max(arr[i] + min(x, y), arr[j] + min(y, z));
		}
	}

	return table[0][n-1];
}

You can run this Function with Similar Main Method.