題目描述: Alice 和 Bob 輪流從一排石頭的前端取 1、2 或 3 個石頭(Alice 先手)。每個石頭有一個分數值(可為負數)。兩人都以最優策略行動。比較最終兩人的總分,回傳 "Alice"、"Bob" 或 "Tie"。
解題思路:
使用動態規劃。定義 dp[i] 為當前玩家從位置 i 開始取石頭時,能獲得的「相對分差」(自己的分數減去對手的分數)。
從右往左計算:
dp[i+j]。dp[i] = max(sum(stones[i..i+j-1]) - dp[i+j]) 對 j = 1, 2, 3。最後看 dp[0]:正數 Alice 贏,負數 Bob 贏,零則平手。
可用後綴和預計算優化取石頭的分數加總。
時間複雜度:O(n) — 每個位置計算常數次(最多 3 次選擇)。
空間複雜度:O(n) — dp 陣列大小。可優化為 O(1),因為只需最近 3 個狀態。
1. Let n = length of stoneValue
2. Create dp array of size n+1, initialized to 0
3. For i from n-1 down to 0:
a. dp[i] = -infinity
b. sum = 0
c. For j = 1 to 3 (while i+j <= n):
- sum += stoneValue[i + j - 1]
- dp[i] = max(dp[i], sum - dp[i + j])
4. If dp[0] > 0 return "Alice"
If dp[0] < 0 return "Bob"
Else return "Tie"記憶化遞迴(Top-Down):定義 solve(i) 為從位置 i 開始的最佳相對分差,遞迴搭配記憶化。邏輯等價但遞迴開銷稍大。
滾動陣列 O(1) 空間:由於 dp[i] 只依賴 dp[i+1]、dp[i+2]、dp[i+3],可用三個變數滾動替代陣列,空間壓縮至 O(1)。