石子游戏

区间DP

石子游戏（每次只能选择 前端或者后端的那一堆）的主要思想是 计算当前局面先手的人选择的那一堆 和 他留给另一个人的局面 从中选出最优解

f[i] [j]考虑区间 [l, r]之间双方都做最优选择 先手后手的最大分差是多少

877. 石子游戏 - 力扣（LeetCode）

dfs(i, j) 双指针表示当前可以取的前端和后端 然后每次取的时候 的好处为 当前先手取得的值减去留给对手的局面所能获得的值

取i和取j两种选择 选较大的

注意当i==j的时候为退出条件

class Solution {
public:
    bool stoneGame(vector<int>& piles) 
    {
        /*
            dfs(i, j) 表示到当前局面先手的人 与另一个的差值
            当i==j的时候不用选 直接返回
            否则选择
        */
        // int n = piles.size();
        // vector<vector<int>>memo(n, vector<int>(n, -1));
        // function<int(int, int)>dfs=[&](int i, int j)->int
        // {
        //     if (i == j)
        //         return piles[i];
        //     if (memo[i][j] != -1)
        //         return memo[i][j];
            
        //     memo[i][j] = max(piles[i] - dfs(i + 1, j), piles[j] - dfs(i, j - 1));
        //     return memo[i][j];
        // };
        // return dfs(0, n - 1);

        int n = piles.size();
        vector<vector<int>>dp(n, vector<int>(n, 0));
    
        for (int i = 0; i < n; i++)
            dp[i][i] = piles[i];
        
        for (int i = n - 2; i >= 0; i--)
        {
            for (int j = i + 1; j < n; j++)
            {
                dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);
            }
        }
        return dp[0][n - 1] >= 0;
    }
};

1690. 石子游戏 VII - 力扣（LeetCode）

这个和上一个有不同的地方 这个题每次是把剩余的全部加起来 所以dfs的时候要先计算出sum （注意每次加之前要先减去当前取的值）相当于dfs多出来一个变量sum

而动态规划写法不能这样 就只能先计算出区间和 每次加上区间和

class Solution {
public:
    int stoneGameVII(vector<int>& nums) 
    {
        /* dfs(i, j) 表示当前局面先手得分和后手的差距
        */
        int n = nums.size();
        // int sum = 0;
        // for (int i = 0; i < n; i++)
        // {
        //     sum += nums[i];
        // }
        // vector<vector<int>>memo(n, vector<int>(n, -1));
        // function<int(int, int, int)>dfs=[&](int i, int j, int now)->int
        // {
        //     if(i == j)
        //         return 0;
        //     if (memo[i][j] != -1)
        //         return memo[i][j];
            
        //     memo[i][j] = max(now - nums[i] - dfs(i + 1, j, now - nums[i]), now - nums[j] - dfs(i, j - 1, now - nums[j]));
        //     return memo[i][j];
        // };
        // return dfs(0, n - 1, sum);
        vector<vector<int>>sum(n, vector<int>(n, 0));
        vector<vector<int>>dp(n, vector<int>(n, 0));
        // 记录i到j的区间和  和前面的题目不一样的地方 区间和
        for (int i = 0; i < n; i++)
        {
            for (int j = i; j < n; j++)
            {
                if (i == j)sum[i][j] = nums[i];
                else sum[i][j] = sum[i][j - 1] + nums[j];
            }
        }

        for (int i = n - 2; i >= 0; i--)
        {
            
            for (int j = i + 1; j < n; j++)
            {
                dp[i][j] = max(sum[i + 1][j] - dp[i + 1][j], sum[i][j - 1] - dp[i][j - 1]);
            }
        }
        return dp[0][n - 1];
    }
};