Link to the problem: https://atcoder.jp/contests/tdpc/tasks/tdpc_game
My approach: This problem is similar to the Deque problem from Educational DP contest (https://atcoder.jp/contests/dp/tasks/dp_l). Using similar ideas I formulated the following recurrence relation with two states i and j, where dp[i][j] is the maximum score Snuke can achieve with i number of elements in pile A and j number of elements in pile B,
dp[i][j] = max(A[i]+min(dp[i-2][j],dp[i-1][j-1]), B[j]+min(dp[i][j-2],dp[i-1][j-1]))
Since most of the times I use top-down approach I tried the same for this problem too. But, the problem is that I am finding it difficult to handle the base cases , I am facing difficulty in transitioning towards the base case. One base case is when both the piles get empty, that is alright, but I am having difficulty in handling the cases where only one pile becomes empty or the number of elements becomes less than one in one or both of the piles.
I looked at some of the submissions but couldn’t find a solution which used top-down approach. Can anyone please share some ideas and code that uses top-down approach to solve this problem?