【題解】LeetCode 1563. Stone Game V

class Solution {
public:
    int n, dp[505][505] = {};
    vector <int> v;
    int f(int l, int r){
        if (l == r) return dp[l][r] = 0;
        if (dp[l][r]) return dp[l][r];
        int tot = 0;
        for (int i = l; i <= r; i++){
            tot += v[i];
        }
        int pre = 0;
        for (int k = l; k < r; k++){
            pre += v[k];
            if (pre <= tot-pre) dp[l][r] = max(dp[l][r], f(l, k)+pre);
            if (pre >= tot-pre) dp[l][r] = max(dp[l][r], f(k+1, r)+(tot-pre));
        }
        return dp[l][r];
    }
    int stoneGameV(vector<int>& stoneValue) {
        n = stoneValue.size();
        v = stoneValue;
        return f(0, n-1);
    }
};