→ lturtsamuel: 雪霸 05/28 12:33
→ oin1104: 蛤 什麼意思 大師 05/28 12:34
→ oin1104: 哇 我懂了 雪霸 05/28 12:35
→ NTHUlagka: 大師 一個最大一個最小不要不信 05/28 13:23
1406. Stone Game III
給你一串 integer array 代表石頭的權重
A 和 B 玩一個輪流拿石頭的遊戲，每次可以從最左邊拿 1~3 顆石頭
用拿到的石頭權重總和來判斷勝負
問你 A 和 B 都使用最佳策略的情況下誰會贏
Example 1:
Input: values = [1,2,3,7]
Output: "Bob"
A 不管拿幾個石頭 B 都會拿走剩下的 每種情況 B 都會贏
Example 2:
Input: values = [1,2,3,-9]
Output: "Alice"
A 會拿 3 顆讓 B 只能拿 -9
Example 3:
Input: values = [1,2,3,6]
Output: "Tie"
A 拿 3 顆可以平手 其他情況 A 都會輸
思路:
1.和前一天的題目很類似 都是用 dp[i] 代表當下拿石頭的那個人
最多能拿到多少石頭或是比對手多多少石頭
有一點我之前沒想通的是
我以為 A 的目標是要多拿石頭 B 的目標是要讓 A 少拿石頭
所以分了兩個 dp 出來
但其實 B 的目標和 A 一樣 都是要讓自己拿越多石頭越好
自己多拿其實就等於對手少拿 兩個人用的 dp 其實是一樣的
2.dp[i] 代表當回合行動的那個人 往後最多能比對手多多少石頭
dp[i] = max(抓一顆 - dp[i+1], 抓兩顆 - dp[i+2], 抓三顆 - dp[i+3])
dp[i+1] 就代表對手從 i+1 顆石頭開始抓 能比你多多少 所以你的結果要減掉他
然後從抓一到三顆裡選一個最好的策略 也就是選最大值
class Solution:
def stoneGameIII(self, stoneValue: List[int]) -> str:
n = len(stoneValue)
dp = [0]*(n+1)
for i in range(n-1, -1, -1):
dp[i] = max([sum(stoneValue[i:k]) - dp[k] for k in range(i+1,
min(n+1, i+4))])
return 'Tie' if dp[i] == 0 else 'Alice' if dp[i] > 0 else 'Bob'
可以注意到 dp[i] 只跟 dp[i+1~i+3] 有關 所以空間複雜度可以再優化變成 O(1)
--
蛤?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.252.3.181 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1685248342.A.228.html