Leetcode Problem 1140. Stone Game II

Algorithm

1. Define a recursive function f(p, i, m) with memoization.
2. If i == n, return 0 (base case).
3. If dp[p][i][m] != -1, return dp[p][i][m] (memoized result).
4. Initialize variables s and res for the current move.
5. Iterate over x from 1 to min(2m, n - i).
   • Update s with the sum of stones in the x piles.
   • If p == 0, update res with s + f(1, i + x, max(m, x)) if it's larger.
   • If p == 1, update res with f(0, i + x, max(m, x)) if it's smaller.
6. Store res in dp[p][i][m].
7. Return res.
8. Initialize dp with -1 and call f(0, 0, 1).