1140. Stone Game II

class Solution {
    public int stoneGameII(int[] piles) {
        int n = piles.length;
        int[] suffixSum = new int[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            suffixSum[i] = suffixSum[i + 1] + piles[i];
        }

        Integer[][] memo = new Integer[n][n + 1];
        return solve(0, 1, piles, suffixSum, memo);
    }

    private int solve(int i, int m, int[] piles, int[] suffixSum, Integer[][] memo) {
        int n = piles.length;

        // Current player can grab everything left (X can reach the end)
        if (i + 2 * m >= n) {
            return suffixSum[i];
        }

        if (memo[i][m] != null) {
            return memo[i][m];
        }

        int best = 0;
        for (int x = 1; x <= 2 * m; x++) {
            int opponentGets = solve(i + x, Math.max(m, x), piles, suffixSum, memo);
            best = Math.max(best, suffixSum[i] - opponentGets);
        }

        memo[i][m] = best;
        return best;
    }
}

class Solution:
    def stoneGameII(self, piles):
        n = len(piles)

        # Suffix sum
        suffix = [0] * (n + 1)

        for i in range(n - 1, -1, -1):
            suffix[i] = suffix[i + 1] + piles[i]

        memo = {}

        def solve(i, m):
            # Can take all remaining piles
            if i + 2 * m >= n:
                return suffix[i]

            if (i, m) in memo:
                return memo[(i, m)]

            best = 0

            for x in range(1, 2 * m + 1):
                opponent = solve(
                    i + x,
                    max(m, x)
                )

                current = suffix[i] - opponent
                best = max(best, current)

            memo[(i, m)] = best
            return best

        return solve(0, 1)

class Solution {
public:
    int stoneGameII(vector<int>& piles) {
        int n = piles.size();

        vector<int> suffix(n + 1, 0);

        for (int i = n - 1; i >= 0; i--) {
            suffix[i] = suffix[i + 1] + piles[i];
        }

        vector<vector<int>> memo(n, vector<int>(n + 1, -1));

        return solve(0, 1, piles, suffix, memo);
    }

private:
    int solve(
        int i,
        int m,
        vector<int>& piles,
        vector<int>& suffix,
        vector<vector<int>>& memo
    ) {
        int n = piles.size();

        // Current player can take all remaining piles
        if (i + 2 * m >= n) {
            return suffix[i];
        }

        if (memo[i][m] != -1) {
            return memo[i][m];
        }

        int best = 0;

        for (int x = 1; x <= 2 * m; x++) {
            int opponent = solve(
                i + x,
                max(m, x),
                piles,
                suffix,
                memo
            );

            int current = suffix[i] - opponent;

            best = max(best, current);
        }

        return memo[i][m] = best;
    }
};

class Solution {
    stoneGameII(piles) {
        const n = piles.length;

        // Suffix sum
        const suffix = new Array(n + 1).fill(0);

        for (let i = n - 1; i >= 0; i--) {
            suffix[i] = suffix[i + 1] + piles[i];
        }

        const memo = Array.from(
            { length: n },
            () => new Array(n + 1).fill(-1)
        );

        const solve = (i, m) => {
            // Current player can take all remaining piles
            if (i + 2 * m >= n) {
                return suffix[i];
            }

            if (memo[i][m] !== -1) {
                return memo[i][m];
            }

            let best = 0;

            for (let x = 1; x <= 2 * m; x++) {
                const opponent = solve(
                    i + x,
                    Math.max(m, x)
                );

                const current = suffix[i] - opponent;

                best = Math.max(best, current);
            }

            memo[i][m] = best;
            return best;
        };

        return solve(0, 1);
    }
}