1140. Stone Game II (Medium)

寫在前面

大家連假過的好嗎XD？筆者到新加坡玩了一趟，不好意思好幾天沒更新啦~

Question

Alex and Lee continue their games with piles of stones. There are a number of piles arranged in a row , and each pile has a positive integer number of stones piles[i]. The objective of the game is to end with the most stones.

Alex and Lee take turns, with Alex starting first. Initially, M = 1.

On each player’s turn, that player can take all the stones in the ** first** X remaining piles, where 1 <= X <= 2M. Then, we set M = max(M, X).

The game continues until all the stones have been taken.

Assuming Alex and Lee play optimally, return the maximum number of stones Alex can get.

Example 1

1
2
3

Input: piles = [2,7,9,4,4]
Output: 10
Explanation:  If Alex takes one pile at the beginning, Lee takes two piles, then Alex takes 2 piles again. Alex can get 2 + 4 + 4 = 10 piles in total. If Alex takes two piles at the beginning, then Lee can take all three piles left. In this case, Alex get 2 + 7 = 9 piles in total. So we return 10 since it's larger.

Constraints

• 1 <= piles.length <= 100
• 1 <= piles[i] <= 10 ^ 4

分析/解題

聽說之前有人一直嗆說怎麼都沒人能夠將1140這題講清楚？

這題其實題目不難理解：
Alex和Lee兩個人玩搶石頭的遊戲，石頭被分成數堆，
使用piles[i]來記錄，遊戲目的是在結尾時拿到最多的石頭。
Alex和Lee輪流拿石頭(Alex先 )，最開始的時候M設定為1 。
每次玩家要決定拿剩下的前X堆的所有石頭 (必須按順序不可以跳過 )，
X的範圍是1 ≤ X ≤ 2M；接下來就要依照X來更新M：M = max(M, X)

直到所有石頭都被拿光，遊戲就結束了。
假定Alex和Lee都以最佳化的狀況來玩這個遊戲(play optimally)，
回傳Alex在遊戲結束時最多能拿到的石頭。

在所謂"play optimally"的遊戲中，
我們會假設參與的玩家都清楚知道所有人的策略 ，
並且選擇對自己利益最大的選擇 。
依照這樣子的概念，我們其實可以感覺到前後會有所關聯，
因為對於雙方來說都是想要最大化自己拿到的石頭 ；
又，自己拿到最多，就意味著對方拿到最少 ，
所以這點同時還隱含了中間的可能會有一些判斷，
比如像是X這類型的變數對於同樣從第i堆開始來說，
要走哪個方向又會都有各自的分支，需要好好考慮才行。

我們先假定有一個函數dp，
這個函數可以計算當現在要從pile[i]開始拿的時候，
(也就是0~i-1堆都被拿光了)
輪到的玩家在這次及這輪以後所能拿到的石頭數的最大值。
顯然這還會有另一個變數M，
因為M能夠決定這輪最大可以拿到的堆數(2M)。
因此我們將這個函數表示成dp(i, M)。

先討論一個最簡單的狀況：
當i+2M ≥ n-1 的時候，(假設總石頭的堆數是n)
表示這個玩家可以直接選擇將剩下的石堆全取走 ，
就會是他所能拿到的石頭量的最大值。
(因為遊戲就結束了，另一個玩家什麼都拿不到)
所以這個就會是這個dp的確定值 的部分了。

接下來我們討論另一個狀況：(假設是A跟B玩家輪流拿石頭)
假設A玩家取了x堆 ，接下來會發生什麼事情呢？
輪到下一個玩家B了，對吧？
那麼玩家要從i+x堆 的位置開始拿取，
而此時的M按照遊戲規則是max(M,x) 。
由於B同樣也是play optimally ，
所以B也想最大限度的在這整場遊戲中獲得較多的石頭 ，
故對B而言在i+x堆開始拿取的數字按照定義就是dp(i+x, max(M,x)) 。

那麼關鍵來了：
對於dp(i,M) 而言，固定不變的會是從pile[i]到最後的石堆的石頭總量 ，
我們暫時先命名為Si, Si = pile[i]~ pile[N-1]的和 。
所以會變動的就只有B拿的部分而已。
所以我們可以得到dp(i, M) = Si - dp(i+x, max(M, x)) 。

又實際上我們一開始也不知道x應該取多少會最好，
所以x的範圍一樣是1~2M ，也就是我們要在x是這個範圍的所有狀況下，
找出dp(i+x, max(M, x))的最小值，從而得到dp(i, M) 。
(因為想要A拿的最多，就是要B拿的最少 ，故要取後者的最小值)

在實務上，我們可以拿前面的piles來計算Si，只要一路從尾到頭 ，
將piles的値往回加即可(因為Si = piles[i]piles[N-1]的和)。
我們需要一個二維陣列dp[][]，
第一個維度表示i (範圍是**0n-1** )
第二個維度表示M (範圍是1~(n-1)/2 + 1 ，但為了方便起見，
我們陣列只使用1開始的部分以避免位移，
所以再加一以後，我們第二維的長度會是**(n+1)/2 + 1** )

我們整理一下實際的演算流程。
主函式中:

1. 從尾到頭 將piles[i+1] 加到piles[i] 上，
   讓piles[i]現在代表從第i堆開始的所有石頭數 。
2. 新增一個二維陣列dp[][] 以表示在**(i, M)** 條件下所能取得石頭的最大値。
3. 呼叫helper函式來遞迴 處理。
   在helper函式中:
4. 如果i已經走超過了則回傳0 (表遊戲結束)
5. 如果2*M >= len(piles) - i則回傳piles[i] (一口氣取完剩下的石頭 )
6. 當dp[i][M]尚未被計算出値的時候，
   遞迴搜尋dp[i+x][max(M,x)]的最小值 ，(x範圍是1~2*M)
   (已知値的話則直接代入)
7. dp[i][M]等於piles[i]減去前述的最小值
8. 回傳dp[i][M]

依此，寫成程式碼：

Java

Python的部分，可將遞迴的部分搭配
for x in range(1, 2 * M + 1) 看起來會更簡潔。

Python

Python的部份根據大神lee215的解答，還可以做一些簡化：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def stoneGameII(self, A: List[int]) -> int:
        N = len(A)
        for i in range(N - 2, -1, -1):
            A[i] += A[i + 1]
        from functools import lru_cache
        @lru_cache(None)
        def dp(i, m):
            if i + 2 * m >= N: return A[i]
            return A[i] - min(dp(i + x, max(m, x)) for x in range(1, 2 * m + 1))
        return dp(0, 1)

lru_cache 可以將函式已經計算過的結果直接快取放置在記憶體中，
當再次需要計算値的時候，不經過計算，直接將値回傳 。

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(N³)/O(N²)，因為記錄所有解要對應到二維陣列，
而對於每一個陣列解都需要往下搜尋O(N)的長度來比較得出最小值。)

「為什麼要記錄一個dp的陣列？不能直接靠遞迴記錄嗎 ？」
(遞迴記錄同樣要使用記憶體空間 ，且因為中間拆解時，
可能會有重複的(i, M)出現，不先記錄的話會造成有重複計算的狀況。 )

「這題是否可以用迭代法解？」
(可以，請參閱yzstone的解法。)

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~