PROBLEM LINK:
Author: Zi Song Yeoh
DIFFICULTY:
EASY
PREREQUISITES:
Dynamic Programming
PROBLEM:
There’re 2 stacks of coins. Flippy and Fluffy takes coins on top of the stack alternately. What is the difference between Flippy and Fluffy’s score at the end of the game?
EXPLANATION:
At first, one might think of the obvious greedy solution, i.e. take the coin that worth the most every time. However, one can come up with an example where the greedy solution fails. (though random cases are strong enough to fail greedy solutions)
The trick here is to note that the game can be defined by two integers, (i, j), the size of the first stack and the size of the second stack. Thus, we can let dp[i][j] be the value of the game when Player 1 moves first and the piles have i and j coins respectively.
Now, the recurrence for the dp is simple. We just have to consider which coin we pick at each state and we can finish the dp in O(n^2) time. See the code for the details of the dp.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.