Optimal Strategy for a Game
You are given an array A of size N. The array contains integers and is of even length. The elements of the array represent N coin of values x1, x2, ... ,xn. The rule of game is:
- Each of the players gets alternative turns.
- In each turn, a player selects either the first or last coin from the row, removes it
- permanently, and receives the value of the coin.
- Both the player plays in an optimal way, i.e., both want to maximize total winning money.
You need to determine the maximum possible amount of money you can win if you start the game.
Input
N=4
Array values:
10 30 5 8
Output:
38
Example:
Number of coins: 4
Coin values:
10 30 5 8
To achieve maximum money:
I will pick up 8 first (Not 10. Think Why?)
So the row will be:
10 30 5
The opponent will pick 10 as that's optimal
So the row will be:
30 5
I will pick 30
Opponent will get 5
Total my winnings: 8+30=38
Total opponents winning: 10+5=15
The first thing that comes to our mind that we should go for the greedy method. Since we can only pick either first element or last element, let's pick the local best one, i.e., Pick the one which is maximum of first and last element. Let's see whether such a method would be optimal or not.
Let's take the same example,
Is this optimal? I got less money than the opponent. So we can simply choose the local best one ( Answer of Why), we can't go for greedy.
Let's check what can be optimal strategy,
Say the coins are,
Let,
There at any stage of game
And it's my turn
So, I can either pick xi or xj based on the optimal choice.
So, I will choose xi or xj what gives me maximum.
so,
Above is the recursion and we need to convert it into Dynamic Programming.
Problem Solution:
We need a 2D array to store f(i,j)
Say, DP[n][n] and the result will be DP[0][n-1] //maximum winning for coin 0th to nth (all the coins)
Base case:
To fill rest of the Table using the recursion,
Initial DP table after computing base cases
DP[4][4] // N=4
Filling up the upper triangular matrix
Len=2
Len=3
C++ implementation:
Output
need an explanation for this answer? contact us directly to get an explanation for this answer