【数据结构与算法】之深入解析“石子游戏VII”的求解思路与算法示例

一、题目描述

• 石子游戏中，爱丽丝和鲍勃轮流进行自己的回合，爱丽丝先开始 。
• 有 n 块石子排成一排，每个玩家的回合中，可以从行中 移除 最左边的石头或最右边的石头，并获得与该行中剩余石头值之和相等的得分。当没有石头可移除时，得分较高者获胜。
• 鲍勃发现他总是输掉游戏（可怜的鲍勃，他总是输），所以他决定尽力 减小得分的差值 。爱丽丝的目标是最大限度地 扩大得分的差值。
• 给你一个整数数组 stones ，其中 stones[i] 表示从左边开始的第 i 个石头的值，如果爱丽丝和鲍勃都发挥出最佳水平 ，请返回他们得分的差值。
• 示例 1：

输入：stones = [5,3,1,4,2]
输出：6
解释：
- 爱丽丝移除 2 ，得分 5 + 3 + 1 + 4 = 13。游戏情况：爱丽丝 = 13，鲍勃 = 0 ，石子 = [5,3,1,4]。
- 鲍勃移除 5 ，得分 3 + 1 + 4 = 8。游戏情况：爱丽丝 = 13 ，鲍勃 = 8，石子 = [3,1,4]。
- 爱丽丝移除 3 ，得分 1 + 4 = 5。游戏情况：爱丽丝 = 18，鲍勃 = 8，石子 = [1,4]。
- 鲍勃移除 1 ，得分 4。游戏情况：爱丽丝 = 18，鲍勃 = 12，石子 = [4]。
- 爱丽丝移除 4 ，得分 0。游戏情况：爱丽丝 = 18，鲍勃 = 12，石子 = []。
得分的差值 18 - 12 = 6 。

• 示例 2：

输入：stones = [7,90,5,1,100,10,10,2]
输出：122

二、求解算法

① 动态规划

• 一个数组 dp 保存从下标 j 到 j+i-1 的差值，一个数组 cache 保存从 j 到 j+i-1 的元素之和；
• 长度 i 从 2 到 n 递增，当前 dp[j][j+i-1] 的值，是 max (取掉最左值的剩余元素和减去 dp[j+1][j+i-1]，去掉最右值的剩余元素和减去 dp[j][j+i-2])；
• 对于上面的中的 max 里面的解释，假如当前玩家是爱丽丝，当前数组 dp 取掉两边任一边的值后，剩下元素组成的数组以鲍勃为首开始取值，这时鲍勃得分必高于爱丽丝，对于爱丽丝得分贡献是负，因此应取爱丽丝当前得分减掉之后鲍勃与爱丽丝得分差值的最大值。
• Java 示例：

class Solution {
    public int stoneGameVII(int[] stones) {
        int n = stones.length;
        int[][] dp = new int[n][n];
        int[][] sum = new int[n][n];
        for(int len=2; len<=n; len++){
            for(int i=0; i<=n-len; i++){
                if(len==2){
                    dp[i][i+1] = Math.max(stones[i], stones[i+1]);
                    sum[i][i+1] = stones[i] + stones[i+1];
                }else{
                    // 1.Alice删掉最右的元素后，得分sum[i][i+len-2]
                    // 之后的操作每一回合Bob的分数一定大于Alice，总计比Alice多dp[i][i+len-2]分
                    // 所以dp[i][i+len-1]=sum[i][i+len-2]-dp[i][i+len-2]
                    // 2.Alice删掉最左的元素后，得分sum[i+1][i+len-1]
                    // 之后的操作每一回合Bob的分数一定大于Alice，总计比Alice多dp[i+1][i+len-1]分
                    // 所以dp[i][i+len-1]=sum[i+1][i+len-1]-dp[i+1][i+len-1]
                    // 按题意，dp[i][i+len-1]取两种情况的较大者
                    dp[i][i+len-1] = Math.max(sum[i][i+len-2]-dp[i][i+len-2], sum[i+1][i+len-1]-dp[i+1][i+len-1]);
                    sum[i][i+len-1] = sum[i+1][i+len-1] + stones[i];
                }
            }
        }
        return dp[0][n-1];
    }
}

② 博弈思路

• 首先明确：谁是先手谁的得分就最大。
• 对于 dp[i][j] 定义为区间 [i,j]，我们要的结果，在区间 [i, j]，dp[i][j] = 先手的总分 - 后手的总分；
• 如果 dp[i][j]这个区间当前是鲍勃操作，那么鲍勃的得分一定最大；选择去掉 stones[i] 后当前的分数为 sum(stones[i + 1], stones[j])，那么区间 [i + 1, j]鲍勃的得分是多少呢？不用管它，dp[i + 1][j] 一定为对手爱丽丝作为先手得到的结果，因为谁先手谁的得分最大，则 dp[i + 1][j] = 爱丽丝得分 - 鲍勃的得分；
• sum(stones[i + 1], stones[j]) - dp[i + 1][j]
  = 鲍勃当前操作得分 - （爱丽丝的总分 - 鲍勃的总分）
  = 鲍勃当前操作得分 + 鲍勃的总分 - 爱丽丝的总分
  = 鲍勃新的总分 - 爱丽丝的总分 > 0（谁先手谁最大）。
• 如果去掉 stones[j] 则原理同上。
• 如果当前 dp[i][j] 是爱丽丝，则将上面的叙述中爱丽丝和鲍勃名字互换。
• 对于爱丽丝，我们很好理解为什么要最大化：dp[i][j] = max(sum(stones[i + 1], stones[j]) - dp[i + 1][j], sum(stones[i], stones[j - 1]) - dp[i][j - 1])；那么鲍勃为什么也要最大化 dp[i][j] 呢，因为爱丽丝先手，鲍勃必输，题目给出了。所以只有当鲍勃操作时 dp[i][j] 最大，才能让爱丽丝操作时得到的结果最小，满足鲍勃的野心，爱丽丝当前操作得分 - (鲍勃的总分 - 爱丽丝的总分)(鲍勃操作时的最大化差值)。
• 基础情况为只有 2 堆石子，值最大的那堆为答案，所以从只有 2 堆石子开始往上进行状态转移。
• C++ 示例：

class Solution {
public:
    int stoneGameVII(vector<int>& stones) {
        vector<vector<int>>dp(stones.size(), vector<int>(stones.size(),0));
        vector<int>sums(stones.size() + 1, 0);
        for(int i = 0;i < stones.size();++i)
            sums[i + 1] = sums[i] + stones[i];
        for(int i = dp.size() - 2; i >= 0; --i) {
            for(int j = i + 1;j < dp[i].size();++j)
                dp[i][j] = max(sums[j + 1] - sums[i + 1] - dp[i + 1][j], sums[j] - sums[i] - dp[i][j - 1]);
        }
        return dp.front().back();
    }
};

三、博客之星

• 今年是我第一次参加博客之星，需要各位大佬的支持，麻烦百忙之中，抽出一点宝贵的时间，给我投一下票：https://bbs.csdn.net/topics/603955258 给我一个五星（列表会一一全部回复），不胜感激！