寫(xiě)在前面

這周周賽的最后一題，經(jīng)典遞推博弈論，但是沒(méi)想出來(lái)，通過(guò)學(xué)習(xí)看懂了推理過(guò)程，還順便學(xué)會(huì)了這種通過(guò)前綴的方式優(yōu)化DP，收獲良多。

題目

核心思路

通過(guò)理解題意，不難發(fā)現(xiàn)，當(dāng)取走左邊若干個(gè)石子后，對(duì)右邊石子原來(lái)的分?jǐn)?shù)是沒(méi)有影響的，仍是前綴和，所以預(yù)處理一個(gè)前綴和是很顯然的。

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

游戲過(guò)程我們不妨先不考慮時(shí)間的要求，直接通過(guò)暴力模擬來(lái)解決。

暴力法

暴力法直接模擬游戲過(guò)程，需要注意每一輪得到的結(jié)果都是這一輪的玩家期望得分差值的最大值。如果當(dāng)前已經(jīng)取到第i (1 <= i <= n)塊石子，那么這一輪可以取到的結(jié)果solve(i)就是從i到n中選擇一個(gè)位置j，使得sum[j] - (下一輪對(duì)手的得分)最大，這里的sum[j]就是這一輪的得分，由于要保證雙方均采用最優(yōu)策略，下一輪對(duì)手也會(huì)選擇最大的得分差值，所以相當(dāng)于求解sum[j] - solve(j + 1)的最大值。

暴力法代碼

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

記憶化遞歸O(N ^ 2)

完全模擬達(dá)到指數(shù)級(jí)別的時(shí)間復(fù)雜度，肯定需要進(jìn)行優(yōu)化，遞歸加優(yōu)化最常見(jiàn)的就是加一個(gè)備忘錄，寫(xiě)成記憶化遞歸。

O(N ^ 2)遞歸代碼

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

記憶化過(guò)程還是很簡(jiǎn)單的，直接加個(gè)備忘錄就可以了，不過(guò)這樣還是O(N ^ 2)的時(shí)間復(fù)雜度，還是會(huì)超時(shí)的。

前綴優(yōu)化DP

在記憶化中，每次遞歸都要從當(dāng)前位置向后遍歷找到最大的滿足條件的值，時(shí)間消耗較大，而每個(gè)位置都只與他后邊的值有關(guān)，我們不妨來(lái)看一下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))

而后邊這一段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))
這樣我們就可以得到優(yōu)化到O(N)時(shí)間復(fù)雜度的代碼了

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

當(dāng)然遞歸可以完成，迭代也同樣可以，不過(guò)迭代DP是自底向上求解，在這道題里也就是從dp[n]開(kāi)始一直求到dp[2]，逆序遞推即可

O(N)動(dòng)態(tài)規(guī)劃代碼

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

        int[] dp = new int[n + 1];
        dp[n] = sum[n];

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

可以發(fā)現(xiàn)dp[i]只與dp[i + 1]有關(guān)，經(jīng)典的空間優(yōu)化，用一個(gè)變量代替dp數(shù)組即可

O(N)動(dòng)態(tài)規(guī)劃優(yōu)化空間代碼

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

        int res = sum[n];

        for(int i = n - 1; i >= 2; i--){
            res = Math.max(res, sum[i] - res);
        }
        return res;
    }
}

總結(jié)

博弈論的問(wèn)題也做過(guò)幾道了，還是不太能抓得住要領(lǐng)，不過(guò)這種優(yōu)化DP的方法還是很值得學(xué)習(xí)的，希望可以越來(lái)越強(qiáng)。
如果文章有寫(xiě)的不對(duì)的地方，還請(qǐng)指出，感謝相遇~~