刷 dp 時看到了博弈論（Game theory，也可以翻賽局理論）的 tag，感覺蠻有趣的就來寫看看了。Leetcode 上打 game theory 的題目有二十幾題，我原本以為只會有個位數題，這數量倒是超乎想像。

877. Stone Game 這題可以用 dp 來解，兩個人輪流做出選擇，決定要拿走最前或最後的石頭，最後依照重量和判定獲勝方。dp 解法可以看簡中版力叩的官方題解，有詳細的推導流程。這個方法是用表格來記錄先後手的最大差距，這次先手代表下次會是後手，所以可以從 [i+1, j] 和 [i, j-1] 這兩段的結果推測出 [i, j] 的最優解。

博弈論解法是另外一個領域。第一眼看到解法居然只有 return True 其實挺錯愕，然後開始懷疑這是不是在鑽漏洞。不過博弈論的一個核心概念就是：經過推演去判斷先／後手是否有必勝解。

在已知全局訊息的狀況下，先手可以影響後手能做的選擇。像是這題的限制下，可以（在最初）把石頭依照順序分成單／雙數堆，然後先手透過每次的決策迫使，後手只能選擇另一堆。因此，先手總是可以先辨認總和高的堆並以此獲勝。

class Solution:
    def stoneGame(self, piles: List[int]) -> bool:
        n = len(piles)
        arr = [[0 for _ in range(n)] for _ in range(n)]
        for i in range(n):
            arr[i][i] = piles[i]

        for i in range(1, n):
            for j in range(n-i):
                arr[j][i] = max(arr[j][j]-arr[j+1][i] ,arr[i][i]-arr[j][i-1])

        return arr[0][-1] > 0

• Game theory
  • 877. Stone Game

Total Count: 18