LeetCode 1140 Stone Game II - Implementation

Here's the full solution:

function stoneGameII(piles)
    n := length of piles
    suffix := array of size n + 1
    suffix[n] := 0
    for i := n - 1 down to 0
        suffix[i] := suffix[i + 1] + piles[i]
    dp := 2D (two-dimensional) array [n + 1][n + 1], all -1
    return solve(0, 1)

function solve(i, M)
    if i >= n then
        return 0
    if i + 2 * M >= n then
        return suffix[i]
    if dp[i][M] != -1 then
        return dp[i][M]
    best := 0
    for X := 1 to 2 * M
        opponent := solve(i + X, max(M, X))
        myStones := suffix[i] - opponent
        best := max(best, myStones)
    dp[i][M] := best
    return best

Time: $O(n^3)$. Space: $O(n^2)$.

Time complexity: $O(n^3)$.

Space complexity: $O(n^2)$.