解題說明
Stone Game III
題目描述： Alice 和 Bob 輪流從一排石頭的前端取 1、2 或 3 個石頭（Alice 先手）。每個石頭有一個分數值（可為負數）。兩人都以最優策略行動。比較最終兩人的總分，回傳 "Alice"、"Bob" 或 "Tie"。
解題思路：
使用動態規劃。定義 dp[i] 為當前玩家從位置 i 開始取石頭時，能獲得的「相對分差」（自己的分數減去對手的分數）。
從右往左計算：
- 當前玩家可以取 1、2 或 3 個石頭（索引 i 到 i+j-1），獲得這些石頭的分數。
- 取完後對手從位置 i+j 開始，對手的相對分差為
dp[i+j]。 - 因此：
dp[i] = max(sum(stones[i..i+j-1]) - dp[i+j])對 j = 1, 2, 3。
最後看 dp[0]：正數 Alice 贏，負數 Bob 贏，零則平手。
可用後綴和預計算優化取石頭的分數加總。
C++ 解法
複雜度分析
時間複雜度：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)。
延伸思考
- 若每次可以取 1 到 m 個石頭（m 為參數），時間複雜度如何變化？
- 石頭的分數都為正數時，Alice 是否一定不會輸？為什麼？
- 若改為「從前端或後端取」（像 Stone Game I），DP 狀態需要怎麼修改？