1563. Stone Game V

class Solution {
    private int[] prefixSum;
    private int[][] memo;

    public int stoneGameV(int[] stoneValue) {
        int n = stoneValue.length;
        prefixSum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + stoneValue[i];
        }

        memo = new int[n][n];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }

        return solve(0, n - 1);
    }

    private int solve(int l, int r) {
        if (l == r) return 0;
        if (memo[l][r] != -1) return memo[l][r];

        int best = 0;
        for (int m = l; m < r; m++) {
            int leftSum = prefixSum[m + 1] - prefixSum[l];
            int rightSum = prefixSum[r + 1] - prefixSum[m + 1];

            int score;
            if (leftSum < rightSum) {
                score = leftSum + solve(l, m);
            } else if (leftSum > rightSum) {
                score = rightSum + solve(m + 1, r);
            } else {
                score = leftSum + Math.max(solve(l, m), solve(m + 1, r));
            }

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

        memo[l][r] = best;
        return best;
    }
}

class Solution:
    def stoneGameV(self, stoneValue):
        n = len(stoneValue)

        prefixSum = [0] * (n + 1)

        for i in range(n):
            prefixSum[i + 1] = prefixSum[i] + stoneValue[i]

        memo = [[-1] * n for _ in range(n)]

        def solve(l, r):
            if l == r:
                return 0

            if memo[l][r] != -1:
                return memo[l][r]

            best = 0

            for m in range(l, r):
                leftSum = prefixSum[m + 1] - prefixSum[l]
                rightSum = prefixSum[r + 1] - prefixSum[m + 1]

                if leftSum < rightSum:
                    score = leftSum + solve(l, m)

                elif leftSum > rightSum:
                    score = rightSum + solve(m + 1, r)

                else:
                    score = leftSum + max(
                        solve(l, m),
                        solve(m + 1, r)
                    )

                best = max(best, score)

            memo[l][r] = best
            return best

        return solve(0, n - 1)

class Solution {
public:
    vector<int> prefixSum;
    vector<vector<int>> memo;

    int solve(int l, int r) {
        if (l == r) {
            return 0;
        }

        if (memo[l][r] != -1) {
            return memo[l][r];
        }

        int best = 0;

        for (int m = l; m < r; m++) {
            int leftSum = prefixSum[m + 1] - prefixSum[l];
            int rightSum = prefixSum[r + 1] - prefixSum[m + 1];

            int score;

            if (leftSum < rightSum) {
                score = leftSum + solve(l, m);
            } 
            else if (leftSum > rightSum) {
                score = rightSum + solve(m + 1, r);
            } 
            else {
                score = leftSum + max(
                    solve(l, m),
                    solve(m + 1, r)
                );
            }

            best = max(best, score);
        }

        return memo[l][r] = best;
    }

    int stoneGameV(vector<int>& stoneValue) {
        int n = stoneValue.size();

        prefixSum.resize(n + 1, 0);

        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + stoneValue[i];
        }

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

        return solve(0, n - 1);
    }
};

/**
 * @param {number[]} stoneValue
 * @return {number}
 */
var stoneGameV = function(stoneValue) {
    const n = stoneValue.length;

    const prefixSum = new Array(n + 1).fill(0);

    for (let i = 0; i < n; i++) {
        prefixSum[i + 1] = prefixSum[i] + stoneValue[i];
    }

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

    function solve(l, r) {
        if (l === r) {
            return 0;
        }

        if (memo[l][r] !== -1) {
            return memo[l][r];
        }

        let best = 0;

        for (let m = l; m < r; m++) {
            const leftSum = prefixSum[m + 1] - prefixSum[l];
            const rightSum = prefixSum[r + 1] - prefixSum[m + 1];

            let score;

            if (leftSum < rightSum) {
                score = leftSum + solve(l, m);
            } 
            else if (leftSum > rightSum) {
                score = rightSum + solve(m + 1, r);
            } 
            else {
                score = leftSum + Math.max(
                    solve(l, m),
                    solve(m + 1, r)
                );
            }

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

        memo[l][r] = best;
        return best;
    }

    return solve(0, n - 1);
};