主題

LeetCode - 877. Stone Game 解題心得

Not In My Back Yard | 2022-01-05 00:00:01 | 巴幣 0 | 人氣 131

題目連結:


題目意譯:
Alex 和 Lee 對著幾堆石頭玩著一個遊戲。現在有偶數堆的石頭排成一列,且每堆有正整數數目的石頭 piles[i]。

遊戲的目的是結束擁有最多的石頭。石頭總數為奇數,所以不會平手。

Alex 和 Lee 輪流,由 Alex 作為先手。每回合,一位玩家從石頭列的開頭或是結尾拿走一整堆的石頭。此步驟重複至沒有石頭堆剩下為止,而此時有著最多石頭的人則為贏家。

假設 Alex 和 Lee 按最佳策略遊玩,回傳真(True)若且唯若 Alex 將贏得遊戲。

限制:
2 ≦ piles.length ≦ 500
piles.length 為偶數。
1 ≦ piles[i] ≦ 500
sum(piles) 為奇數。



範例測資:
範例 1:
輸入: piles = [5,3,4,5]
輸出: true
解釋:
Alex 先發,且只能拿第一個 5 或最後一個 5。
這裡假設他拿第一個 5,所以石頭列變成了 [3, 4, 5]。
如果 Lee 拿走 3,則遊戲版面變為 [4, 5],則 Alex 拿走 5 以 10 分贏得勝利。
如果 Lee 拿走 5,則遊戲版面變為 [4, 5],則 Alex 拿走 4 以 9 分贏得勝利。
這顯示了拿走第一個 5 對於 Alex 是贏得勝利的一手,所以我們回傳真。


解題思維:
乍看之下是個普通的動態規劃(Dynamic Programming,DP)題型,而 DP 也確實可以解出此題。但是此題有著相當特殊的性質——因為堆數是偶數且石頭總顆數是奇數,因此可推論出 Alex 必贏。



論證如下:
兩堆的情況:很直觀,Alex 挑大的即可;

四堆的情況:假設四堆數量為 a 、 b 、 c 、 d,則 Alex 將會有方式可以一定拿到 [a, c] 這兩堆或是 [b, d] 這兩堆。而根據石頭總數是奇數,一定有一個組合比較大,因此 Alex 挑大的組合即可獲勝;

任意偶數 n 堆的情況:類似四堆時的狀況。假設每堆石頭數量為 p0 、 p1 、 …… 、 pn,則 Alex 可以必定拿到 i 為偶數的 pi 們或是 i 奇數的 pi 們。而當中有一個組合一定比較大,因此挑大的必贏。




那為何 Alex 可以必拿到偶數(或奇數,這邊用偶數說明)索引值的石頭堆呢?

一開始 Alex 會拿走 p0,因此現在列上的開頭結尾都是奇數索引值的。也就導致 Lee 一定只能拿到奇數索引值的石頭堆,並且將會使另一個偶數索引值之堆顯現於開頭或結尾使得 Alex 可以拿取。而此性質將可以重複到石頭堆通通被拿光光為止。

所以 Alex 可以拿走所有偶數索引值的石頭堆。奇數索引值也是與上同理。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作