【資料結構與演算法】之深入決議“石子游戲VIII”的求解思路與演算法示例

一、題目描述

• Alice 和 Bob 玩一個游戲，兩人輪流操作， Alice 先手，總共有 n 個石子排成一行，
• 輪到某個玩家的回合時，如果石子的數目 大于 1 ，他將執行以下操作：
• • 選擇一個整數 x > 1 ，并且 移除 最左邊的 x 個石子；
• • 將移除的石子價值之和累加到該玩家的分數中；
• • 將一個新的石子放在最左邊，且新石子的值為被移除石子值之和；
• 當只剩下一個石子時，游戲結束，
• Alice 和 Bob 的 分數之差 為 (Alice 的分數 - Bob 的分數) ，Alice 的目標是最大化分數差，Bob 的目標是最小化分數差，
• 給你一個長度為 n 的整數陣列 stones ，其中 stones[i] 是 從左邊起第 i 個石子的價值，請你回傳在雙方都采用最優策略的情況下，Alice 和 Bob 的分數之差，
• 示例 1：

輸入：stones = [-1,2,-3,4,-5]
輸出：5
解釋：
- Alice 移除最左邊的 4 個石子，得分增加 (-1) + 2 + (-3) + 4 = 2 ，并且將一個價值為 2 的石子放在最左邊，stones = [2,-5] ，
- Bob 移除最左邊的 2 個石子，得分增加 2 + (-5) = -3 ，并且將一個價值為 -3 的石子放在最左邊，stones = [-3] ，
兩者分數之差為 2 - (-3) = 5，

• 示例 2：

輸入：stones = [7,-6,5,10,5,-2,-6]
輸出：13
解釋：
- Alice 移除所有石子，得分增加 7 + (-6) + 5 + 10 + 5 + (-2) + (-6) = 13 ，并且將一個價值為 13 的石子放在最左邊，stones = [13] ，
兩者分數之差為 13 - 0 = 13，

• 示例 3：

輸入：stones = [-10,-12]
輸出：-22
解釋：
- Alice 只有一種操作，就是移除所有石子，得分增加 (-10) + (-12) = -22 ，并且將一個價值為 -22 的石子放在最左邊，stones = [-22] ，
兩者分數之差為 (-22) - 0 = -22，

二、求解演算法

① 動態規劃（Leetcode 官方解法）

• 在任意一名玩家進行操作之后，剩余的所有石子的價值總和不會發生變化，對于每一步操作，玩家可以把「最左側」的 x 枚石子進行「價值合并」，并獲得與「價值」等價的分數，因此，最左側的石子的價值一定是 stones 的某一個前綴和，即玩家在每一輪獲得的分數一定是初始陣列 stones 的某一個前綴和，
• 可以將題目中的游戲轉化成如下等價的形式：
• • 求出 stones 的前綴和陣列 pre，其中：

• • Alice 和 Bob 依次在陣列 pre 上進行操作，并且 Alice 先手，在一次操作中，當前玩家可以選擇一個下標 u，獲得 pre[u] 的分數：
• • • 如果當前玩家是 Alice 并且是首次操作，那么 u 不能為 0，對應到題目中的游戲規則，即為「選擇的石子數量
      x 必須大于 1」；
• • • 對于其余的情況，如果對手的上一次操作選擇的下標是 v，那么必須有 u>v，對應到題目中的游戲規則，即為「對手上一次操作合并了若干枚石子，使得最左側的石子的價值為 pre[v]」，同時「當前玩家合并了從最左側的石子開始，到原本在陣列 stones 中下標為 u 的石子為止的所有石子，使得最左側的石子的價值為 pre[u]」，
• • 設陣列 stones 和 pre 的長度為 n，如果當前玩家選擇了下標 n?1，那么它就會合并剩余的所有石子，游戲結束，
• 可以使用基于博弈思想的動態規劃解決上述的游戲，設 f(i) 表示當 Alice 可以選擇的下標 u 在 [i,n) 范圍內時，Alice 與 Bob 分數的最大差值，在進行狀態轉移時，可以考慮 Alice 是否選擇了 i 作為下標 u；
• • 如果 Alice 沒有選擇 i 作為下標 u，那么她需要在 [i+1,n) 的范圍內進行選擇，因此有狀態轉移方程：

• • 如果 Alice 選擇了 i 作為下標 u，那么她獲得了 pre[i] 的分數，并且輪到 Bob 在剩余的范圍 [i+1,n) 中進行選擇，由于 Bob 會采用最優策略，因此在 [i+1,n) 的范圍內，Bob 與 Alice 分數的最大差值就為 f[i+1]，因此有狀態轉移方程：

• 由于 Alice 會采用最優策略，因此狀態轉移選擇二者中的較大值：

• 從 i=n?1 開始倒序地計算所有的狀態，最終的答案即為 f[1]，
• C++ 示例：

class Solution {
public:
    int stoneGameVIII(vector<int>& stones) {
        int n = stones.size();
        vector<int> pre;
        partial_sum(stones.begin(), stones.end(), back_inserter(pre));
        vector<int> f(n);
        f[n - 1] = pre[n - 1];
        for (int i = n - 2; i >= 1; --i) {
            f[i] = max(f[i + 1], pre[i] - f[i + 1]);
        }
        return f[1];
    }
};

• 復雜度分析：
• • 時間復雜度：O(n)，
• • 空間復雜度：O(n)，即為陣列 pre 和 f 需要的空間，

② 暴力法

• 核心思路：通過理解題意，不難發現，當取走左邊若干個石子后，對右邊石子原來的分數是沒有影響的，仍是前綴和，所以預處理一個前綴和是很顯然的，

int[] sum = new int[n + 1];
for(int i = 0; i < n; i++) { 
  sum[i + 1] = sum[i] + stones[i];
}

• 游戲程序不妨先不考慮時間的要求，直接通過暴力模擬來解決，
• 暴力法直接模擬游戲程序，需要注意每一輪得到的結果都是這一輪的玩家期望得分差值的最大值，如果當前已經取到第 i (1 <= i <= n) 塊石子，那么這一輪可以取到的結果 solve(i) 就是從 i 到 n 中選擇一個位置 j，使得 sum[j] - (下一輪對手的得分)最大，這里的 sum[j] 就是這一輪的得分，由于要保證雙方均采用最優策略，下一輪對手也會選擇最大的得分差值，所以相當于求解 sum[j] - solve(j + 1) 的最大值，
• Java 示例：

class Solution {

    int n;
    int[] stones;
    int[] sum;

    public int stoneGameVIII(int[] stones) {
        n = stones.length;
        this.stones = stones;
        sum = new int[n + 1];
        
        for(int i = 0; i < n; i++) sum[i + 1] = sum[i] + stones[i];

        return solve(2);
    }

    public int solve(int idx){
        if(idx == n) return sum[idx];

        int res = sum[n];
        for(int i = idx; i < n; i++){
            res = Math.max(res, sum[i] - solve(i + 1));
        }
        return res;
    }
}

• 記憶化遞回：完全模擬達到指數級別的時間復雜度，肯定需要進行優化，遞回加優化最常見的就是加一個備忘錄：

class Solution {

    int n;
    int[] stones;
    int[] sum;
    Integer[] memo;

    public int stoneGameVIII(int[] stones) {
        n = stones.length;
        this.stones = stones;
        
        memo = new Integer[n + 1];
        sum = new int[n + 1];

        for(int i = 0; i < n; i++) sum[i + 1] = sum[i] + stones[i];
        memo[n] = sum[n];
        return solve(2);
    }

    public int solve(int idx){
        if(memo[idx] != null) return memo[idx];

        int res = sum[n];
        for(int i = idx; i < n; i++){
            res = Math.max(res, sum[i] - solve(i + 1));
        }
        return memo[idx] = res;
    }
}

• 記憶化程序還是很簡單的，直接加個備忘錄就可以了，不過這樣還是O(N²)的時間復雜度，還是會超時的，
• 在記憶化中，每次遞回都要從當前位置向后遍歷找到最大的滿足條件的值，時間消耗較大，而每個位置都只與他后邊的值有關，不妨來看一下 solve(x) 的值到底等于什么：

solve(x) = max(sum[x] - solve(x + 1), sum[x + 1] - solve(x + 2), ... , sum[n - 1] - solve(n), sum[n] - solve(n + 1))

• 而后邊這一段 max(sum[x + 1] - solve(x + 2), … , sum[n - 1] - solve(n), sum[n] - solve(n + 1))，恰好是 solve(x + 1) 的值，帶入也就得到：

solve(x) = Math.max(solve(x + 1), sum[x] - solve(x + 1))

• 這樣就可以得到優化到 O(N) 時間復雜度的代碼，

class Solution {

    int n;
    int[] stones;
    int[] sum;
    Integer[] memo;

    public int stoneGameVIII(int[] stones) {
        n = stones.length;
        this.stones = stones;
        
        memo = new Integer[n + 1];
        sum = new int[n + 1];

        for(int i = 0; i < n; i++) sum[i + 1] = sum[i] + stones[i];
        memo[n] = sum[n];
        return solve(2);
    }

    public int solve(int idx){
        if(memo[idx] != null) return memo[idx];

        int res = Math.max(solve(idx + 1), sum[idx] - solve(idx + 1));
        return memo[idx] = res;
    }
}

三、博客之星

• 今年是我第一次參加博客之星，需要各位大佬的支持，麻煩百忙之中，抽出一點寶貴的時間，給我投一下票：https://bbs.csdn.net/topics/603955258 給我一個五星（串列會一一全部回復），不勝感激！