LeetCode 区间dp

1553. 吃掉 N 个橘子的最少天数

class Solution {
public:
    int minCost(int n2, vector<int> &cuts) {
        vector<int> s;
        sort(cuts.begin(),cuts.end());
        cuts.push_back(n2);
        s.push_back(0);
        for (auto i:cuts) {
            s.push_back(i);
        }

        const int N = 200;
        int n = s.size() - 1;
        int f[N][N];
        memset(f, 0, sizeof f);

        for (int len = 2; len <= n; len++)  // 先从小到大循环区间长度
            for (int i = 1; i + len - 1 <= n; i++)  // 再从左端点开始
            {
                int l = i, r = i + len - 1;
                f[l][r] = 1e8;
                for (int k = l; k < r; k++)   // 再枚举决策
                    f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
            }
        return f[1][n];
    }
};

5498. 石子游戏 V

class Solution {
public:
    int dp[501][501]; // 记忆化数组，用于避免重复计算
    int sum[501];

    int dfs(int l, int r) {
        if(dp[l][r] != -1) { //已经计算过该子问题了，直接范围答案
            return dp[l][r];
        }
        if(l == r) { // 终止条件，直接获得答案
            dp[l][r] = 0;
        } else {
            //递进阶段，根据题意，求解最大值；
            int val = 0;
            for(int i = l; i< r; i++) {
                int s1 = sum[i] - sum[l-1];
                int s2 = sum[r] - sum[i];

                if(s1 < s2) { // 根据题意，只能取后半段
                    val = max(val, s1 + dfs(l, i));
                } else if(s1 > s2){ // 根据题意，只能取前半段
                    val = max(val, s2 + dfs(i+1, r));
                } else { // 相等时，可任意选择~
                    val = max(dfs(l, i), dfs(i+1, r)) + s1;
                }
            }
            //回归阶段，更新答案
            dp[l][r] = val;
        }
        return dp[l][r];
    }

    int stoneGameV(vector<int>& stoneValue) {
        memset(dp, -1, sizeof(dp));

        //出来一下前缀和
        sum[0] = 0;
        for(int i = 0; i < stoneValue.size(); i++) {
            sum[i+1] = sum[i] + stoneValue[i];
        }

        return dfs(1, stoneValue.size());
    }
};