Hey Programmers, Hope you all are safe and doing well.

I am a beginner in DP, and while solving the atcoder dp series, Problem K (Stones) , I am not able to pass all sets of test cases. Also this I am not able to analyse whether its a DP or greedy problem.

Here is My Solution :.

**My Logic** : If we can reduce the no.of stones(k) to something where the opponent cannot make a next move, I win. Else I simply reduce the min no. (mn) of the given array from the no.of stones.

Can you please clear my confusion ? It will be helpful if you can point out the test case...where my solution goes wrong. Thank You.

Hey, your logic is not correct because you have ignored the fact that both the players are playing optimally at every turn. So, it is not necessary at a particular k it will be optimum to always choose the minimum a[i] in A.

This problem is an extension of classic coin change problem where you have to try all the a[i] possible from set A on every state k (0<=k<=K). You can take a look at my solution. My solution to K

Here dp[i] is 1 if for this state player who starts the game wins and 0 if the other player wins. Our answer would dp[k].

Thanks for the explanation. Actually I knew that something is wrong in optimal decision making but was not getting the right example to prove my mistake. Thankfully I got it...

Now I can try out the DP solution.

Hey, I'm also relatively new to dp and wrote a code to same problem and my approach was almost similar to yours but instead I have used a 2-D dp array with states being : 1st — No. of stones and 2nd — index upto which array is considered. But it is not working in all the test cases could you help me by pointing out my mistake. Here is my code. Thanks

My solution to K i thought greedy can't work and then thought of dp