在賽局理論中，有一類的問題是允許所有玩家看到場面上的所有遊戲資訊的。在遊戲進行中不引入隨機變數 (a.k.a 不擲骰子) 的狀況下，這類問題叫做完全訊息賽局(Game with complete information)。通常這類問題在初始盤面開始時，就能夠決定輸贏。而動態規劃，就是一個此時可以拿來找出誰輸誰贏的重要手段！

大家還記得小時候看到的「搶30遊戲」嗎？甲、乙兩個人輪流數數，一次可以把數字加上 1, 2, 或 3，最先數到 30 的人就獲勝了。這個問題就是經典的完全訊息賽局。

而用資訊方法解決這類賽局的策略也很簡單：對於一個狀態而言，把所有可能的下一步都嘗試一遍，如果這些方法中有一個能讓接下來接手的玩家「必敗」，那麼這個當前狀態就「必勝」了！

好久沒寫 Leetcode 了呢，今天來寫個一兩個簡單的賽局題目吧！

Exercise 41: Leetcode 1025 - Divisor Game

題目連結

https://leetcode.com/problems/divisor-game/

題目敘述

Alice 和 Bob 玩一個數字遊戲。對於一個數字 N，由 Alice 開始，兩人輪流進行操作：每次找一個 N 的正因數 x，介於 0 和 N 之間，然後把 N 換成 N-x。無法操作的人輸。給定 N 的值，請問 Alice 能獲勝嗎？

解題思考

我們令 dp(i) 代表初始值是 i 的話是否能獲勝。顯然狀態轉移就是：如果所有的 dp(i-x) 都是 False 的話，它就是 True 了。反之為 False。

參考程式碼 (Python3)

class Solution:
    def divisorGame(self, N: int) -> bool:
        win = [False] * (N+1)
        for n in range(2, N+1):
            for x in range(1, n):
                if n % x == 0 and win[n-x] == False:
                    win[n] = True
                    break
        return win[N]

Exercise 42: Leetcode 877 - Stone Game

題目連結

https://leetcode.com/problems/stone-game/

題目敘述

有偶數堆石頭排成一排，每一堆分別有 piles[i] 個。現在 Alex 與 Lee 輪流拿石頭，Alex 先拿。他們每次可以拿當前最左邊或最右邊的石頭。最後拿的石頭總數較多的人就獲勝了，已知石頭總數是奇數（代表一定有人能獲勝，不會平手），請問誰能獲勝？

解題思考

對於動態規劃經驗豐富的我們，可以利用 dp(i, j) 紀錄下從 i 到 j 這段，先手和後手分別拿石頭以後，在「想拿最多石頭、在無法拿較多石頭時，讓對手拿取盡量少的石頭」能夠得到的石頭數量分別是多少？那麼我們可以建立 dp(i, j) ← dp(i+1, j) or dp(i, j+1) 的轉移。最後比較看看誰的石頭多就知道是先手獲勝還是後手獲勝了。

但這題其實更簡單。因為有偶數堆、總和是奇數的關係，我們可以直接證明先手必勝：把石頭堆黑白相間染色，Alex 可以控制遊戲讓兩個玩家永遠選擇同一種顏色的石頭堆去拿。也就是說 Alex 只要一開始選擇總石頭數較多的顏色石頭堆去拿就可以了！

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