[Geeks for Geeks] Pots of Gold Game

Pots of Gold Game

Two players X and Y are playing a game in which there are pots of gold arranged in a line, each containing some gold coins. They get alternating turns 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.

Return the maximum coins X could get while playing the game. Initially, X starts the game.

  • Time : O(n^2)
  • Space : O(n^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
int dp[505][505];
int helper(vector<int>& A, int l, int r) {
if(l > r) return 0;
if(dp[l][r] != -1) return dp[l][r];
int& res = dp[l][r] = INT_MIN;
res = max(res, A[l] - helper(A, l + 1, r));
res = max(res, A[r] - helper(A, l, r - 1));
return res;
}
public:
int maxCoins(vector<int>&A,int n)
{
memset(dp, -1, sizeof dp);
return (helper(A, 0, n - 1) + accumulate(begin(A), end(A), 0)) / 2;
}

Author: Song Hayoung
Link: https://songhayoung.github.io/2022/05/26/PS/GeeksforGeeks/pots-of-gold-game/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.