I am no sure how to go about with this problem. Help would be great!
At the start of the game are two plates of sashimi, containing and pieces respectively. At every turn, a player may eat all the pieces of sashimi on one plate, and redistribute the pieces from the remaining plate to produce two plates containing ⌈ /3 ⌉ and − ⌈ /3 ⌉ pieces respectively. The player who starts the turn with two plates each with one sashimi piece pays the bill. Describe a dynamic programming strategy which avoids paying the bill for each and (if there is a winning move for and ).
Here's my solution. I'm not 100% sure this is dynamic programming, but its definitely using memoization which is a common technique in DP. Here's the intuition.
Suppose your opponent just took their turn and the sushi was split, resulting in having n and m pieces in front of you. Since it is your turn to eat a plate, if you eat the plate with n pieces, you split the plate with m pieces and vice versa if you eat the plate with m pieces.
NOW, suppose both you and your opponent know the optimum strategy for both of these subproblems; that is, if you eat the plate with n pieces, both of you know whether their is a winning move after the split or not (same goes for m pieces). Since it is your turn, your move should be to eat the plate that doesn't give your opponent a winning move. That way, when it is their turn, no matter which plate they decide to eat, they are hooped either way, and you can just keep playing this strategy until the game ends and they lose.
Now for the actual algorithm. First you will need to construct an array A[k]; where k = max{m,n} indexed from 1...k. The indices of this array will represent the number of pieces left over after a split, and the value at each index will represent whether you win or lose if you leave an opponent with this many pieces.
So for A[1] = win. If you leave an opponent with 1 piece, it will get split into to plates of 1 pieces and your opponent loses (so you win).
A[2] = win. Again, the plate will get split into to plates of 1, you win, they lose.
Now for the general case. If you leave your opponent with i pieces, check the value at ⌈i /3 ⌉ and i − ⌈i /3 ⌉. If either of these values = win, then A[i] = lose. This is because you have left your opponent with a winning move and assuming they follow the strategy, the will continue to make winning moves until the end of the game.
IF however, BOTH of these values = lose, then A[i] = win. Now we have left the opponent in a scenario where they cannot possibly make a winning move, so we will win if we stick the algorithm.
Again, this sounds like dynamic programming to me, but I'm rusty so don't quote me.