【資料結構與演算法】之深入決議“石子游戲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 給我一個五星（串列會一一全部回復），不勝感激！