寫在前面
這周周賽的最后一題危喉，經(jīng)典遞推博弈論宋渔，但是沒想出來，通過學(xué)習(xí)看懂了推理過程辜限，還順便學(xué)會了這種通過前綴的方式優(yōu)化DP，收獲良多严蓖。
題目
核心思路
通過理解題意薄嫡，不難發(fā)現(xiàn)，當(dāng)取走左邊若干個石子后颗胡，對右邊石子原來的分數(shù)是沒有影響的毫深，仍是前綴和，所以預(yù)處理一個前綴和是很顯然的毒姨。
int[] sum = new int[n + 1];
for(int i = 0; i < n; i++) {
sum[i + 1] = sum[i] + stones[i];
}
游戲過程我們不妨先不考慮時間的要求哑蔫，直接通過暴力模擬來解決。
暴力法
暴力法直接模擬游戲過程弧呐，需要注意每一輪得到的結(jié)果都是這一輪的玩家期望得分差值的最大值闸迷。如果當(dāng)前已經(jīng)取到第i (1 <= i <= n)塊石子，那么這一輪可以取到的結(jié)果solve(i)就是從i到n中選擇一個位置j俘枫，使得sum[j] - (下一輪對手的得分)最大腥沽，這里的sum[j]就是這一輪的得分，由于要保證雙方均采用最優(yōu)策略鸠蚪，下一輪對手也會選擇最大的得分差值今阳，所以相當(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)
完全模擬達到指數(shù)級別的時間復(fù)雜度茅信，肯定需要進行優(yōu)化盾舌，遞歸加優(yōu)化最常見的就是加一個備忘錄，寫成記憶化遞歸蘸鲸。
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;
}
}
記憶化過程還是很簡單的妖谴，直接加個備忘錄就可以了，不過這樣還是O(N ^ 2)的時間復(fù)雜度棚贾，還是會超時的窖维。
前綴優(yōu)化DP
在記憶化中，每次遞歸都要從當(dāng)前位置向后遍歷找到最大的滿足條件的值妙痹，時間消耗較大铸史，而每個位置都只與他后邊的值有關(guā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))
而后邊這一段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)時間復(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)然遞歸可以完成，迭代也同樣可以崭篡，不過迭代DP是自底向上求解挪哄，在這道題里也就是從dp[n]開始一直求到dp[2]，逆序遞推即可
O(N)動態(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)化迹炼，用一個變量代替dp數(shù)組即可
O(N)動態(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é)
博弈論的問題也做過幾道了，還是不太能抓得住要領(lǐng)颠毙，不過這種優(yōu)化DP的方法還是很值得學(xué)習(xí)的斯入，希望可以越來越強。
如果文章有寫的不對的地方蛀蜜，還請指出刻两，感謝相遇~~
