# Pots of Gold Game – Dynamic Programming

Two-player X and Y are playing Pots of Gold Game where pots of gold arranged in a  line, each containing some gold coins. Both players will get an alternating chance in which the player can pick a pot from one of the ends of the line. The winner is the player who has a higher number of coins at the end. The objective is to maximize the number of coins collected by X, assuming Y also plays optimally. first player i.e. x will start the game.

Example:

``````Input:
arr = {9, 10, 3, 7}

Output:
17``````

As optimum move first player X will choose 7.

Now, the second player has the choice of selecting either 3 or 9 as the max pot of gold player Y select 9

again, player X will choose 10 and Y to have to select 3.

#### Solution:

``````using System;

namespace Array
{
class Program
{
private static int[, ] _memorize;

public static void Main()
{
int[] arr = { 9, 10, 3, 7};
_memorize = new int[arr.Length, arr.Length];
Console.Write(GoldGame(arr, 0, arr.Length - 1));
}

static int GoldGame(int[] arr, int start, int end)
{
if (start == end)
return arr[start];

if (start + 1 == end)
return Math.Max(arr[start], arr[end]);

if (_memorize[start, end] != 0)
return _memorize[start, end];

var playerX = arr[start] + Math.Min(GoldGame(arr, start + 2, end), GoldGame(arr, start + 1, end - 1));
var playerY = arr[end] + Math.Min(GoldGame(arr, start + 1, end - 1), GoldGame(arr, start, end - 2));

_memorize[start, end] = Math.Max(playerX, playerY);

return _memorize[start, end];
}

}
}``````