Pots of gold (DP-06)

There are two players A and B and some pots containing gold arranged in a line each containing some number of gold coins. At any point of time, the players can see the number of gold coins available in the pots. Each player gets alternating turns in which the player picks a pot from one of the ends of the line. The winner is the player which has the higher number of coins at the end. The objective is to maximize the number of coins collected by player A assuming that B also plays optimally and A starts the game.

Sample Input: Coins in pots = { 6, 1, 4, 9, 8, 5 }.
Expected Output: 18
Explanation: We need to return the maximum number of coins that A can achieve and player A starts the game.
A picks up 6. A_Total = 6
B picks up 5. B_Total = 5
A picks up 8. A_Total = 14
B picks up 9. B_Total = 14
A picks up 4. A_Total = 18
B picks up 1. B_Total = 15.
Thus, maximum number of coins collected by A is 18.

Algorithm:

The main idea is to find an optimal way that makes a player win while knowing that the opponent is also playing optimally. For each turn, the player has two choice – Either he can pick a pot from front or rear end. That is, if the pot array is P [ i … j ] , he can pick either i’th or j’th pot.

If the current player chooses i’th pot, the opponent is left with P [ i+1 … j] pots to choose from.
1. If the opponent chooses from pot (i+1), recur for P [ i+2 … j]
2. If the opponent chooses from pot (j), recur for P [ i+1 … j-1 ]

If the current player chooses j’th pot, the opponent is left with P [i … (j-1)] pots to choose from.
1. If the opponent chooses from pot i, recur for P [i+1 … j-1]
2. If the opponent chooses from pot (j-1), recur for P [i … (j-2)]

Since, the opponent is also playing optimally, he will try to minimize the number of gold coins collected by player.

/* Author => Raunak Jain */
#include <bits/stdc++.h>
using namespace std;

int helper(vector<vector<int>> &dp, vector<int> coins, int i, int j){
	if(i==j){
		return coins[i];
	}
	if(i+1==j){
		return max(coins[i], coins[j]);
	}
	if(dp[i][j]==0){
		// if player chooses front pot i, opponent is left to choose
		// from [i+1, j].
		// 1. if opponent chooses front pot i+1, recur for [i+2, j]
		// 2. if opponent chooses rear pot j, recur for [i+1, j-1]
		//opponent will make a choice that will leave the players with minimum coins
		int start = coins[i] + min(helper(dp, coins, i+2, j), helper(dp, coins, i+1, j-1));
		
		int end = coins[j] + min(helper(dp, coins, i+1, j-1), helper(dp, coins, i, j-2));
		dp[i][j] = max(start, end);
	}
	return dp[i][j];
}

int main(){

	vector<int> coins = { 4, 6, 2, 3 };
	vector<vector<int>> dp(4, vector<int>(4, 0));
	cout<<helper(dp, coins, 0, 3);
	
	return 0;
}

Also, take a look at another popular interview question Longest Palindromic Subsequence.

3 comments

Leave a Reply

Your email address will not be published.