anyone please share your approach
Consider only one stack. Let dp[i] store a boolean denoting whether the person whose turn it is will win when there are i coins remaining in the stack.
Following are the base cases:
- i = 0 : since the person whose chance it is has no coins to take, he/she loses. Hence, dp = 0.
- i = 1 : only one coin, the person whose chance it is can take it and win the game. So, dp = 1.
- i = k : the person whose chance it is can select all the k coins and win since the other cannot take any more. Hence, dp[k] = 1.
- i = l : similarly, dp[l] = 1.
Now at each turn a person picks either 1, k, or l coins. To win, one would try to take coins in such a way that with the remaining coins the opponent cannot win. In our case, if either of dp[i-1] , dp[i-k] , dp[i-l] is 0 then dp[i] will be 1 as we can take that may number of coins such that dp[rem] = 0 . But if all of dp[i-1] , dp[i-k] , dp[i-l] are 1 then in all the three possible options, the the game goes to a state where the opponent wins making dp[i] = 0 .
Hence, dp[i] = !(dp[i-1]\&dp[i-k]\&dp[i-l]).
Here is my code: LINK