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"

C++ 程式碼

Runtime: 13 ms, beats 84.51. Memory: 135.94 MB, beats 88.20%.

class Solution {
public:
    string stoneGameIII(vector<int>& stoneValue) {
        int n = (int)stoneValue.size();
        vector<int> dp (n+1, -1000000000);
        dp[n] = 0;
        for(int i = n-1; i >= 0; i--) {
            int val = 0;
            for(int j = 1; j <= 3; j++) {
                if (i+j <= n) {
                    val += stoneValue[i+j-1];
                    dp[i] = max(dp[i], val - dp[i+j]);
                }
            }
        }
        if (dp[0] > 0) return "Alice";
        else if (dp[0] < 0) return "Bob";
        else return "Tie";
    }
};