玩遊戲也能用DP? 石頭遊戲Stone Game II 的最佳策略+影片教學_Leetcode #1140

小松鼠
發佈於演算法專欄 個房間
閱讀時間約 1 分鐘

題目敘述

給定一個piles陣列,裡面對應到每堆石頭的數量。

Alice 和 Bob玩輪流取石頭的遊戲,總共有n堆石頭,每堆的石頭數量有多有少,
初始化窗口參數M=1。

Alice先取,接著Bob,反覆交替,每回合輪到的人可以從當下的位置拿1~X堆,拿走對應的石頭數輛。X值可以介於1~2M。
每回合結束後,遊戲機制會更新M值,讓M值= Max(M, X)。

最後比誰拿到的石頭總數量比較多就獲勝

請問,最後Alice最多可以拿幾顆石頭?

題目額外保證,兩人都用最優策略Optimal來玩,會盡可能讓自己取到最多的石頭


題目的原文敘述


約束條件

Constraints:

  • 1 <= piles.length <= 100

最少一堆石頭,最多100堆石頭。

  • 1 <= piles[i] <= 10^4

每堆石頭的石頭數量介於1~一萬之間。


教學影片



演算法 區間DP 搭配 min/Max

控制當下玩家選擇區間的參數有兩個:

第一個是start,可以選擇的起始點索引。

第二個是窗口參數M,玩家當下這回合可以選X堆,X介於1~2M。


每次選擇都從分支裡面挑一個最佳的,白話地說,就是盡可能壓縮對手的石頭數量

當只有兩名玩家(本題的Alice, Bob)時,
最大化我方拿到的石頭數量 = 最小化對手可以拿到的石頭數量


另外,有一個實用的加速技巧,

為了方便快速計算區間內總共有多少石頭,
可以使用後綴和表格stone_after進行DP計算的預處理


想一下,為什麼此處使用後綴和,而不是前綴和?

因為取石頭一定是從當下的位置往後取,從index start開始往後考慮


區間DP定義

取石頭的區間可以用區間DP來描述。

DP[start, M] = 從start index開始取,可以取1~2M堆,
我方取得的石頭數量最大值。


通則怎麼想呢?

題目說,每回合輪到的人可以取當下的i堆,i = 1~2M

如果取當下的第一堆,那麼對手剩下[start+1, max(1, M)]的區間可以選擇,對手的情況相當於DP[start+1, max(1, M)]。

如果取連續兩堆,那麼對手剩下[start+2, max(2, M)]的區間可以選擇,對手的情況相當於DP[start+2, max(2, M)]。

...推廣到一般化的形式就是

如果取連續兩堆,那麼對手剩下[start+i, max(i, M)]的區間可以選擇,對手的情況相當於DP[start+i, max(i, M)]。


因為我們要的是採取最佳策略,白話的說,就是盡可能壓縮對手的石頭數量

因此,當下的取石頭的最佳策略可以這樣表達

Max(取一堆,連取兩堆、連取三堆、...、連取2M堆)

= stone_after[start] - min( take(start+i, max(i, M)) for i in range(1, 2*M+1) )


遞迴的終止條件(也可以說初始條件)是什麼呢?

就是都取完,已經沒有多餘的石頭可以選擇,這時候start >= N = 石頭總堆樹

DP[start, M] 且 start >= N = 石頭總堆樹
= 0 已經沒有剩下的石頭了


OK,現在DP的定義、通則、終止條件都有了!

寫成對應的DP程式碼即可。

最佳策略取石頭的區間DP程式碼

    def stoneGameII(self, piles: List[int]) -> int:

# total length of piles
N = len(piles)

# total stones of input array
total_stone = sum(piles)

# Table
# key : index
# value: total number of stone after index i
stone_after = [total_stone]

for i in range(1, len(piles)):
stone_after.append( stone_after[-1] - piles[i-1] )

# DP Table
# key: Game state of (start, M)
# value: Max number of stone taken, from state (start, M)
memo = {}
def take(start, M):

# Look-up DP table
if (start, M) in memo:
return memo[(start, M)]

# Start index is out of boundary, take nothing
if start >= N :
memo[(start, M)] = 0
return 0

# Coverage is big enough, take all remaining stones
if start + 2*M >= N:
memo[(start, M)] = stone_after[start]
return stone_after[start]

# Max current turn <=> Min opponent's turn <=> Min next turn
memo[(start, M)] = stone_after[start] - min( take(start+i, max(i, M)) for i in range(1, 2*M+1) )
return memo[(start, M)]


return take(start=0, M=1)

複雜度分析

令 n = len(piles)

時間複雜度 O(n^3)

DP狀態數目依賴於(start, M),二維DP的狀態總數為O(n^2)。

每個狀態在線性時間O(n)掃描窗口1~2M可以求出最佳解。

總共所需時間為O(n^2) * O(n) = O( n^3 )。


空間複雜度 O(n^2)

DP table需要儲存 O(n^2)個狀態,另外DP遞迴的最大深度也是O(n^2)

總共所需空間維O(n^2)。


關鍵知識點

從題目的敘述和範例觀察,最佳選擇策略可以用區間DP描述。

DP的通則可以由選擇的分支推導出來。

當下的取石頭的最佳策略可以這樣表達
Max(取第一堆,連取兩堆、連取三堆、...、連取2M堆)
= stone_after[start] - min( take(start+i, max(i, M)) for i in range(1, 2*M+1) )


這題和前面介紹過的那題遊戲模擬題玩遊戲也可以用DP ? 石頭遊戲 I 的最佳策略_Leetcode #877 非常像喔,用到的最佳化概念也是類似的,

強烈建議讀者一起複習、練習!


Refernce

[1] Stone Game II - LeetCode

52會員
339內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
發表第一個留言支持創作者!
你可能也想看
【親子遊戲】我的垃圾袋不是垃圾,用垃圾袋也可以玩遊戲!其實比起現成的玩具,小孩更喜歡玩「生活用品」,用「垃圾袋」也可以和孩子玩遊戲或變成玩具,怎麼玩?
Thumbnail
avatar
阿妮媽咪
2024-04-29
【Queenie聊教養】結果,玩遊戲也能讓孩子專注又靜心孩子的靜心遊戲充滿了趣味與活力,讓孩子在遊戲中慢慢地安靜下來,甚至平常可以作為孩子的睡眠儀式呢~
Thumbnail
avatar
Queenie's - 淬煉生命的旅程
2023-11-15
玩遊戲也會被騙?Steam爭氣卡假網購、遊戲帳號異常釣魚、代購詐騙樣樣來隨著疫情期間大家玩遊戲的時間變多,遊戲平台Steam、Twitch跟著崛起,也讓詐騙集團開始盯上這個商機,假冒遊戲平台或是推出「代購」的優惠方案,想方設法地從用戶手上騙取個資、帳密、財物等。近期我們發現一個販售「Steam爭氣卡」的詐騙網站,如果你也發現這些特徵,請務必小心!
Thumbnail
avatar
C 琳
2023-07-24
等等黨獲勝啦!! ZOTAC GeForce RTX3050 AMP 精省大師也能玩光追遊戲以萬元出頭的價位,能夠在1080p順跑AAA遊戲的顯示卡來說,ZOTAC GeForce RTX3050 AMP算是相當好的選擇!透過RTX系列顯卡的光追與DLSS人工智慧技術,整體遊戲表現與細節都相當優秀。實際上在玩遊戲時,光追效果能讓遊戲的體驗提升非常多!
Thumbnail
avatar
3Cholic科技情報
2022-07-06
來推一款遊戲吧~玩遊戲也能讓心靜下來 朋友突然推薦我一款說是用心做的遊戲,很有藝術感,閒著沒事可以玩玩 據說整個遊戲就是解謎+聽音樂+享受畫面質感 據說遊戲節奏感慢的很是感人 我想了想,剛好遇到特價,幾十塊不貴我就買了
Thumbnail
avatar
泡澡的太陽
2021-12-24
最近忙著玩遊戲...人生不也是種遊戲?最近,沉迷於電動玩具,喔,抱歉!那是老一派的講法!哈哈哈!反正就不誤正業,不好好讀書,一直打電動啦! 遊戲呢~是限制級遊戲,就是人稱的「小黃遊」~就不講是啥遊戲了! 玩遊戲其實就跟追劇很像,就是人家設計好情節、劇情,就一直給它看下去,若沉迷於劇情,您可能會發現,不就是看著另一個人的人生嗎?若把自己
Thumbnail
avatar
林雲秋
2021-12-06
疫情期間在家玩音樂遊戲也可以不擾鄰眼睛注意看 專心看清楚題目喔 數一數 大的小的 手牽手八分音符看清楚喔 只有兩位八分音符手牽手 四個手牽手可以算對嗎?
Thumbnail
avatar
蕭瑞玲音樂治療隨想
2021-05-25
玩遊戲也能翻轉學習熱情走到玩轉學校的展示區,攤位竟然空無一人!轉眼看到創辦人林哲宇帶著夥伴穿梭在各個攤位。「去年來雜學校有很深的無力感,攤位都像在爭奇鬥艷,要吸引關注,但大家明明都在做一件好的事呀。」哲宇提到去年參展的感想,於是今年決定捨棄空間型的展示空間,踏出自己的展位、去認識更多不同的人,尋找結合彼此專長的合作機會。
Thumbnail
avatar
雜學校
2020-06-04
【菜鳥談】玩遊戲也能紅?憑什麼?──變化多端的網路新產業:實況實況主與觀眾會在這樣的氛圍下,漸漸形成彼此之間熟悉的默契。他們會用像是對待朋友的方式一樣,互相給予回饋。有些實況主甚至會舉辦線下聚會,來與觀眾同樂。 實況之所以吸引人,就是因為它沒有隔閡。
Thumbnail
avatar
Moonrogu
2018-07-24