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));
     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];
  }
  
 }
}