Get Max Coin In Game problem.

In this chapter we shall solve how to get maximum coin in a game problem with help of DP.

Problem Statement:

You and your friend are playing a game to pick numbers from an array of even length. You need to find a solution so that you can pick the maximum sum and you win the game.
Example array
maximum_coin_problem
You are player P1 and your friend is player P2.
Initially you pick 1
Your friend picks 2
You pick 1
Your friend picks 4
Your total = 2
Your friend total = 6
So here you need to come up with a strategy where you will be the winner. We can solve this by DP.
Consider the array:
maximum_coin_problem
Initially below will be our DP array:
maximum_coin_problem
As we have 4 elements, we took 4 x 4 matrix. Let’s start filling the matrix. We shall get the result at [0,3] index.
As there are 2 players, we indicate like [4, 5]. Here the player 1 will have profit 4 and player 5 will have profit 5. It means, player 1 profit will be the 1st element, and player 2 profit will be the 2nd element.
So initially we have only 1 element i.e. 4 and its index is 0.
So if you have only ‘4’, you will choose ‘4’ player 2 will choose 0. As there is only 1 element, and player 1 has chosen it, player 2 will get 0. Hence we can fill our DP array as dp[0,0] = [4,0].
Similarly, if you have only 8 dp[1, 1] =[8, 0]
Similarly, if you have only 1 dp[2, 2] =[1, 0]
Similarly, if you have only 2 dp[3, 3] =[2, 0]
The updated DP table will be
maximum_coin_problem
Now let’s take 2 elements at t time and compute the same.
First you have [4, 8]. Hence player P1 will pick 8 and player 2 will pick 4. Hence dp[0, 1] = [8, 4].
Next you have [8, 1]. Here P1 = 8, P2 =1.
Hence dp[1, 2] = [8, 1].
Next you have [1, 2]. Here P1 = 2, P2 =1.
Hence dp[2, 3] = [2, 1].
Hence our final DP array will be:
maximum_coin_problem
From the above can we derive a DP formula? Yes, we can derive.
Ok, Concentrate below:
For the index dp[0, 1], we have the elements [4, 8]. If the player P1, choose 4, then player P2 choose 8, then again player P1 will have to choose what’s left after player P2 has chosen.
Initially P1 chose 4m P2 chose 8. As the player P2 has chose 8 and it’s index is 1, you need to check the 2nd value in dp[1, 1]. The 2nd value i.e. P2’s value is 0. You add the value that you have selected i.e 4 + 0= 4.
Again if you choose 8 in [4, 8], P2 will choose 4. You need to check the 2nd value for the index [0, 0] i.e 0. You add to the value you have selected i.e 8 + 0 = 8. Now you have 2 values [4, 8]. You need to take the max of the value i.e. 8. Hence we get [8, 4].
Next, we shall select 3 elements [4, 8, 1] and index are [0, 1, 2] and solve with the same approach as above.
So first P1 picks 4, then we need to add with the 2nd value at the index [1,2] ie 4 + 1 = 5.
else P1 picks 1, then we need to add with 2nd value at the index [0, 1] i.e 1 + 4 = 5. In any case, we choose 5.
and P2 will choose 8. Hence for dp[0, 2] = [5, 8]
Now we shall select [8, 1, 2]
If P1 chose 8, we need to add with 2nd value of [2, 3].
8 + 1 = 9
If P1 chose 2, we need to add with 2nd value of [1, 2].
2 + 1 = 3
As max of [9, 3] is 9. P1 will chose 9. P2 will take the next value that we have chosen. i.e P2 will take 1.
Hence dp[1, 3] = [9, 1].
maximum_coin_problem
Now we shall take 4 elements at a time.
[4, 8, 1, 2] and index are [0, 1, 2, 3].
If P1 chose 4 then we need to add with 2nd element at the index [1, 3].
i.e 4 + 1 = 5.
If P1 chose 2 then we need to add with 2nd element at the index [0, 2].
i.e 2 + 8 = 10.
We shall choose 10 as it is max and 2nd player gets 4 + 1 = 5.
Hence final dp[0, 3] = [10, 5].
maximum_coin_problem
Hence the result.
Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *