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)