5498. 石子游戏 V

5498. 石子游戏 V

区间dp

这一题引出了一个很好的思考
为啥记忆化dfs比填表的dp快

• 因为填表dp是自底向上算的，填表dp中，if else 中的每个状态都是从len=2自底向上算出来的

if (left < right) {
    if (v < left + f[i][k])v = left + f[i][k];
} else if (left > right) {
    if (v < right + f[k + 1][j])v = right + f[k + 1][j];
} else {
    if (v < left + max(f[i][k], f[k + 1][j]))
        v = left + max(f[i][k], f[k + 1][j]);
}

• 而记忆化dfs是自顶向下的，记忆化dfs中的 if else 如果判断条件不成立就不会进入那一个条件代码块里的下一层的dfs

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和记忆化dfs的代码

填表dp

填表dp也就最后一个点卡了，其他点都过了

class Solution {
public:
    vector<int> s;

    int get(int l, int r) {
        return s[r] - s[l - 1];
    }

    int stoneGameV(vector<int> &w) {
        int n = w.size();
        s.resize(n + 1);
        for (int i = 1; i <= n; i++)s[i] = s[i - 1] + w[i - 1];
        int f[n+1][n+1];
        memset(f,0,sizeof f);
        
        for (int len = 2; len <= n; len++)
            for (int i = 1; i + len - 1 <= n; i++) {
                int j = i + len - 1;
                int &v = f[i][j];
                for (int k = i; k < j; k++) {
                    int left = get(i, k), right = get(k + 1, j);
                    if (left < right) {
                        if (v < left + f[i][k])v = left + f[i][k];
                    } else if (left > right) {
                        if (v < right + f[k + 1][j])v = right + f[k + 1][j];
                    } else {
                        if (v < left + max(f[i][k], f[k + 1][j]))
                            v = left + max(f[i][k], f[k + 1][j]);
                    }
                }
            }
        return f[1][n];
    }
};

记忆化dfs

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());
    }
};