LeetCode 解題筆記：1406. Stone Game III

作者：王一哲
日期：2026年8月3日


LeetCode 題目連結：1406. Stone Game III

解題想法

困難題。題目給一個長度為 $n$ 的陣列 $stoneValue$ 代表每個石頭的分數，玩家 Alice、Bob 每回合行動時，可以選擇取走目前編號最小的1到3個石頭並獲得這幾個石頭的分數，固定由 Alice 先行動，最後依照總分回傳答案，如果 Alice 總分較高回傳 Alice，如果 Bob 總分較高回傳 Bob，如果平手回傳 Tie。

這題考動態規畫，定義長度為 $n+1$ 的陣列 $dp$，$dp[i]$ 代表剩下 $i$ 個石頭時的最大分差，除了 $dp[n] = 0$，其它項初始化為負無窮大。更新時由 $i = n-1$ 往回更新到 $i = 0$，由於可以選擇拿1到3個石頭，再用一層 for 迴圈跑 $j = 1$ 到 $j = 3$，如果 $i+j \leq n$ 更新目前取石頭的總分 $val += stoneValue[i+j-1]$，$dp[i] = max(dp[i], val - dp[i+j])$。最後依照 $dp[0]$ 的值回傳答案，如果 $dp[0] > 0$ 回傳 Alice，如果 $dp[0] < 0$ 回傳 Bob，如果 $dp[0] = 0$ 回傳 Tie。

Python 程式碼

Runtime: 617 ms, beats 74.25%. Memory: 23.91 MB, beats 71.59%.

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        n = len(stoneValue)
        dp = [float('-inf')] * (n+1)  # dp[i] 代表取第 i 個時剩下的石頭最大分差
        dp[n] = 0  # 沒有剩下的石頭，之後的最大分差為 0
        # 由 stoneValue 後往前取值
        for i in range(n-1, -1, -1):
            val = 0  # 拿走的石頭得分
            for j in range(1, 4):  # 試著拿1、2、3個石頭
                if i + j <= n:  # 避免出界
                    val += stoneValue[i+j-1]  # 加上第 i+j-1 個石頭的分數
                    dp[i] = max(dp[i], val - dp[i+j])  # 更新 dp[i]，可能是 val 減掉對手於 dp[i+j] 的最大分差
        
        if dp[0] > 0: return "Alice"
        elif dp[0] < 0 : return "Bob"
        else: return "Tie"

LeetCode 解題筆記：877. Stone Game

作者：王一哲
日期：2026年8月2日


LeetCode 題目連結：877. Stone Game

解題想法

中等難度題。這題看起來與昨天的 486. Predict the Winner 幾乎一樣，題目給一個陣列 $piless$，兩個玩家 Alice、Bob 每次行動時可以從 $piles$ 兩端選取並移除一堆石頭，Alice 先行動，如果 Alice 拿到比較多的石頭回傳 True。這題一 樣可以用動態規畫解題，建立一個 $n \times n$ 的二維陣列 $dp[i][j]$ 代表可選的值剩下 $piles[i]$ ~ $piles[j]$ 時目前行動玩家與另一人的最大分差。更新狀態時有 2 種選擇：

1. 行動1，選 $piles[i]$，新的區間為 $piles[i+1]$ ~ $piles[j]$，最大分差為 $piles[i] - dp[i+1][j]$
2. 行動2，選 $piles[j]$，新的區間為 $piles[i] ~ piles[j-1]$，最大分差為 $piles[j] - dp[i][j-1]$

玩家採用最佳策略，從行動1、2之中選分數高的，因此 $$ dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1]) $$ 當 $i = j$ 時，只能選擇一個數字，$dp[i][j] = piles[i]$。更新 $dp$ 時，要從長度 $2$ 開始，直到長度等於 $n$ 為止，因為長度較長的狀態，是基於長度較短的狀態更新數值。更新完畢之後，如果 $dp[0][n-1] \geq 0$，Alice 獲勝，回傳 True。

但是這題多加了兩個條件：$piles$ 的長度為偶數，$piles$ 所有的數量加起來為奇數，答案一定是 True。因為 Alice 可以選擇取走所有奇數索引值或是偶數索引值的石頭堆，選擇總數多的石頭堆就能獲勝。

Python 程式碼

dp. Runtime: 127 ms, beats 41.69%. Memory: 25.47 MB, beats 34.68%.

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)  # 長度
        # dp[i][j] 範圍為 piles[i] ~ piles[j] 對應的最大分差
        dp = [[0]*n for _ in range(n)]
        # 初始化，只剩下一堆能選
        for i in range(n):
            dp[i][i] = piles[i]
        # 更新 dp，外層更新長度 2 ~ n，內層更新起點 i = 0 ~ n - len
        for length in range(2, n+1):
            for i in range(n - length + 1):
                j = i + length - 1
                dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])
        # 如果 dp[0][n-1] > 0，Alice 獲勝，回傳 True
        return dp[0][n-1] > 0

Runtime: 0 ms, beats 100.00%. Memory: 19.33 MB, beats 55.87%.

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        return True

LeetCode 解題筆記：486. Predict the Winner

作者：王一哲
日期：2026年8月1日


LeetCode 題目連結：486. Predict the Winner

解題想法

中等難度題。題目給一個陣列 $nums$，兩個玩家 A、B 每次行動時可以從 $nums$ 兩端選取並移除一個數字，獲得這個數字的分數，玩家 A 先行動，如果玩家 A 總分大於等於玩家 B，回傳 True。這題很適合用動態規畫解題，建立一個 $n \times n$ 的二維陣列 $dp[i][j]$ 代表可選數字剩下 $nums[i]$ ~ $nums[j]$ 時目前行動玩家與另一人的最大分差。更新狀態時有 2 種選擇：

1. 行動1，選 $nums[i]$，新的區間為 $nums[i+1]$ ~ $nums[j]$，最大分差為 $nums[i] - dp[i+1][j]$
2. 行動2，選 $nums[j]$，新的區間為 $nums[i] ~ nums[j-1]$，最大分差為 $nums[j] - dp[i][j-1]$

玩家採用最佳策略，從行動1、2之中選分數高的，因此 $$ dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]) $$ 當 $i = j$ 時，只能選擇一個數字，$dp[i][j] = nums[i]$。更新 $dp$ 時，要從長度 $2$ 開始，直到長度等於 $n$ 為止，因為長度較長的狀態，是基於長度較短的狀態更新數值。更新完畢之後，如果 $dp[0][n-1] \geq 0$，玩家 A 獲勝，回傳 True。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.11 MB, beats 94.32%.

class Solution:
    def predictTheWinner(self, nums: List[int]) -> bool:
        n = len(nums)
        # 初始化 dp
        dp = [[0]*n for _ in range(n)]
        for i in range(n):
            dp[i][i] = nums[i]
        # 由長度 2 開始填表格，直到長度 n 為止
        for length in range(2, n+1):
            for i in range(n - length + 1):  # 起點
                j = i + length - 1  # 終點
                dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1])
        # 回傳答案
        return dp[0][n-1] >= 0