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].