iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 26
1
Software Development

動態規劃百題之經典、理論與實作系列 第 26

Day 26: 賽局問題裡面判斷輸贏的過程也是動態規劃!

在賽局理論中,有一類的問題是允許所有玩家看到場面上的所有遊戲資訊的。在遊戲進行中不引入隨機變數 (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

上一篇
Day 25: 除了序列以外在計算幾何中也可以動態規劃!
下一篇
Day 27: 隨機走訪等機率的計算也能用動態規劃達成!
系列文
動態規劃百題之經典、理論與實作30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

1 則留言

0
polymath
iT邦新手 5 級 ‧ 2020-05-17 04:55:29

Stone Game 這好像在耍人...感覺可以拿去夜市騙人XDD

卡卡恩 iT邦新手 4 級 ‧ 2020-05-17 06:53:19 檢舉

XDDDD 我倒是曾經有閃過開一間刷題咖啡廳的念頭XD
寫完 10 題程式題目可以換一杯珍珠奶茶之類的

polymath iT邦新手 5 級 ‧ 2020-05-17 17:55:44 檢舉

弄成像7 Billion Humans on Steam這種遊戲好像不錯,這樣不會寫程式的也能玩。

leokqq27 iT邦新手 5 級 ‧ 2022-01-18 16:46:33 檢舉

這個店怕會有很多CV工程師XD

我要留言

立即登入留言