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));
Console.ReadLine();
}
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];
}
}
}