玩遊戲也能用DP? 石頭遊戲Stone Game II 的最佳策略+影片教學_Leetcode #1140
題目敘述
給定一個piles陣列，裡面對應到每堆石頭的數量。
Alice 和 Bob玩輪流取石頭的遊戲，總共有n堆石頭，每堆的石頭數量有多有少，
初始化窗口參數M=1。
Alice先取，接著Bob，反覆交替，每回合輪到的人可以從當下的位置拿1~X堆，拿走對應的石頭數輛。X值可以介於1~2M。
每回合結束後，遊戲機制會更新M值，讓M值= Max(M, X)。
最後比誰拿到的石頭總數量比較多就獲勝。
請問，最後Alice最多可以拿幾顆石頭?
題目額外保證，兩人都用最優策略Optimal來玩，會盡可能讓自己取到最多的石頭。
約束條件
Constraints:
1 <= piles.length <= 100
最少一堆石頭，最多100堆石頭。
1 <= piles[i] <= 10^4
每堆石頭的石頭數量介於1~一萬之間。
教學影片
演算法 區間DP 搭配 min/Max
控制當下玩家選擇區間的參數有兩個:
第一個是start，可以選擇的起始點索引。
第二個是窗口參數M，玩家當下這回合可以選X堆，X介於1~2M。
每次選擇都從分支裡面挑一個最佳的，白話地說，就是盡可能壓縮對手的石頭數量。
當只有兩名玩家(本題的Alice, Bob)時，
最大化我方拿到的石頭數量 = 最小化對手可以拿到的石頭數量。
另外，有一個實用的加速技巧，
為了方便快速計算區間內總共有多少石頭，
可以使用後綴和表格stone_after進行DP計算的預處理。
想一下，為什麼此處使用後綴和，而不是前綴和?
因為取石頭一定是從當下的位置往後取，從index start開始往後考慮。
區間DP定義
取石頭的區間可以用區間DP來描述。
DP[start, M] = 從start index開始取，可以取1~2M堆，
我方取得的石頭數量最大值。
通則怎麼想呢?
題目說，每回合輪到的人可以取當下的i堆，i = 1~2M。
如果取當下的第一堆，那麼對手剩下[start+1, max(1, M)]的區間可以選擇，對手的情況相當於DP[start+1, max(1, M)]。
如果取連續兩堆，那麼對手剩下[start+2, max(2, M)]的區間可以選擇，對手的情況相當於DP[start+2, max(2, M)]。
...推廣到一般化的形式就是
如果取連續兩堆，那麼對手剩下[start+i, max(i, M)]的區間可以選擇，對手的情況相當於DP[start+i, max(i, M)]。
因為我們要的是採取最佳策略，白話的說，就是盡可能壓縮對手的石頭數量。
因此，當下的取石頭的最佳策略可以這樣表達
Max(取一堆，連取兩堆、連取三堆、...、連取2M堆)
= stone_after[start] - min( take(start+i, max(i, M)) for i in range(1, 2*M+1) )
遞迴的終止條件(也可以說初始條件)是什麼呢?
就是都取完，已經沒有多餘的石頭可以選擇，這時候start >= N = 石頭總堆樹
DP[start, M] 且 start >= N = 石頭總堆樹
= 0 已經沒有剩下的石頭了
OK，現在DP的定義、通則、終止條件都有了!
寫成對應的DP程式碼即可。
最佳策略取石頭的區間DP程式碼
def stoneGameII(self, piles: List[int]) -> int:
# total length of piles
N = len(piles)
# total stones of input array
total_stone = sum(piles)
# Table
# key : index
# value: total number of stone after index i
stone_after = [total_stone]
for i in range(1, len(piles)):
stone_after.append( stone_after[-1] - piles[i-1] )
# DP Table
# key: Game state of (start, M)
# value: Max number of stone taken, from state (start, M)
memo = {}
def take(start, M):
# Look-up DP table
if (start, M) in memo:
return memo[(start, M)]
# Start index is out of boundary, take nothing
if start >= N :
memo[(start, M)] = 0
return 0
# Coverage is big enough, take all remaining stones
if start + 2*M >= N:
memo[(start, M)] = stone_after[start]
return stone_after[start]
# Max current turn <=> Min opponent's turn <=> Min next turn
memo[(start, M)] = stone_after[start] - min( take(start+i, max(i, M)) for i in range(1, 2*M+1) )
return memo[(start, M)]
return take(start=0, M=1)
複雜度分析
令 n = len(piles)
時間複雜度 O(n^3)
DP狀態數目依賴於(start, M)，二維DP的狀態總數為O(n^2)。
每個狀態在線性時間O(n)掃描窗口1~2M可以求出最佳解。
總共所需時間為O(n^2) * O(n) = O( n^3 )。
空間複雜度 O(n^2)
DP table需要儲存 O(n^2)個狀態，另外DP遞迴的最大深度也是O(n^2)
總共所需空間維O(n^2)。
關鍵知識點
從題目的敘述和範例觀察，最佳選擇策略可以用區間DP描述。
DP的通則可以由選擇的分支推導出來。
當下的取石頭的最佳策略可以這樣表達
Max(取第一堆，連取兩堆、連取三堆、...、連取2M堆)
= stone_after[start] - min( take(start+i, max(i, M)) for i in range(1, 2*M+1) )
這題和前面介紹過的那題遊戲模擬題玩遊戲也可以用DP ? 石頭遊戲 I 的最佳策略_Leetcode #877 非常像喔，用到的最佳化概念也是類似的，
強烈建議讀者一起複習、練習!
Refernce
