1. 石子游戏 Stone Game IV
Alice 和 Bob 两个人轮流玩一个游戏，Alice 先手。
一开始，有 n 个石子堆在一起。每个人轮流操作，正在操作的玩家可以从石子堆里拿走 任意 非零 平方数 个石子。
如果石子堆里没有石子了，则无法操作的玩家输掉游戏。
给你正整数 n ，且已知两个人都采取最优策略。如果 Alice 会赢得比赛，那么返回 True ，否则返回 False 。
示例 1：
输入：n = 1
输出：true
解释：Alice 拿走 1 个石子并赢得胜利，因为 Bob 无法进行任何操作。
示例 2：
输入：n = 2
输出：false
解释：Alice 只能拿走 1 个石子，然后 Bob 拿走最后一个石子并赢得胜利（2 -> 1 -> 0）。
示例 3：
输入：n = 4
输出：true
解释：n 已经是一个平方数，Alice 可以一次全拿掉 4 个石子并赢得胜利（4 -> 0）。
示例 4：
输入：n = 7
输出：false
解释：当 Bob 采取最优策略时，Alice 无法赢得比赛。
如果 Alice 一开始拿走 4 个石子， Bob 会拿走 1 个石子，然后 Alice 只能拿走 1 个石子，Bob 拿走最后一个石子并赢得胜利（7 -> 3 -> 2 -> 1 -> 0）。
如果 Alice 一开始拿走 1 个石子， Bob 会拿走 4 个石子，然后 Alice 只能拿走 1 个石子，Bob 拿走最后一个石子并赢得胜利（7 -> 6 -> 2 -> 1 -> 0）。
示例 5：
输入：n = 17
输出：false
解释：如果 Bob 采取最优策略，Alice 无法赢得胜利。
提示：
1 <= n <= 10^5
代码：
class Solution: def stoneGameIV(self, n: int) -> bool: dp = [False] * (n + 1) for i in range(1, n + 1): for j in range(1, int(i**0.5) + 1): if not dp[i - j*j]: dp[i] = True break return dp[n] #%% s = Solution() print(s.stoneGameIV(1)) print(s.stoneGameIV(2)) print(s.stoneGameIV(4)) print(s.stoneGameIV(7)) print(s.stoneGameIV(17))
输出：
True
False
True
False
False
2. 石子游戏 Stone Game V
几块石子 排成一行 ，每块石子都有一个关联值，关联值为整数，由数组 stoneValue 给出。
游戏中的每一轮：Alice 会将这行石子分成两个 非空行（即，左侧行和右侧行）；Bob 负责计算每一行的值，即此行中所有石子的值的总和。Bob 会丢弃值最大的行，Alice 的得分为剩下那行的值（每轮累加）。如果两行的值相等，Bob 让 Alice 决定丢弃哪一行。下一轮从剩下的那一行开始。
只 剩下一块石子 时，游戏结束。Alice 的分数最初为 0 。
返回 Alice 能够获得的最大分数 。
示例 1：
输入：stoneValue = [6,2,3,4,5,5]
输出：18
解释：在第一轮中，Alice 将行划分为 [6，2，3]，[4，5，5] 。左行的值是 11 ，右行的值是 14 。Bob 丢弃了右行，Alice 的分数现在是 11 。
在第二轮中，Alice 将行分成 [6]，[2，3] 。这一次 Bob 扔掉了左行，Alice 的分数变成了 16（11 + 5）。
最后一轮 Alice 只能将行分成 [2]，[3] 。Bob 扔掉右行，Alice 的分数现在是 18（16 + 2）。游戏结束，因为这行只剩下一块石头了。
示例 2：
输入：stoneValue = [7,7,7,7,7,7,7]
输出：28
示例 3：
输入：stoneValue = [4]
输出：0
提示：
1 <= stoneValue.length <= 500
1 <= stoneValue[i] <= 10^6
代码1： 动态规划
from typing import List class Solution: def stoneGameV(self, stoneValue: List[int]) -> int: n = len(stoneValue) presum = [0] * (n + 1) for i in range(n): presum[i + 1] = presum[i] + stoneValue[i] dp = [[0] * n for _ in range(n)] for i in range(n): dp[i][i] = 0 for i in range(n - 2, -1, -1): for j in range(i + 1, n): for k in range(i, j): leftsum = presum[k + 1] - presum[i] rightsum = presum[j + 1] - presum[k + 1] if leftsum < rightsum: dp[i][j] = max(dp[i][j], dp[i][k] + leftsum) elif leftsum > rightsum: dp[i][j] = max(dp[i][j], dp[k + 1][j] + rightsum) else: dp[i][j] = max(dp[i][j], dp[i][k] + leftsum, dp[k + 1][j] + rightsum) return dp[0][n - 1] #%% s = Solution() stoneValue = [6,2,3,4,5,5] print(s.stoneGameV(stoneValue)) stoneValue = [7,7,7,7,7,7,7] print(s.stoneGameV(stoneValue))
代码2：记忆化搜索
from typing import List class Solution: def stoneGameV(self, stoneValue: List[int]) -> int: n = len(stoneValue) presum = [0] * (n + 1) for i in range(n): presum[i + 1] = presum[i] + stoneValue[i] memo = [[-1] * n for _ in range(n)] def dfs(i, j): if memo[i][j] != -1: return memo[i][j] if i == j: memo[i][j] = 0 return 0 res = 0 for k in range(i, j): leftsum = presum[k + 1] - presum[i] rightsum = presum[j + 1] - presum[k + 1] if leftsum < rightsum: res = max(res, dfs(i, k) + leftsum) elif leftsum > rightsum: res = max(res, dfs(k + 1, j) + rightsum) else: res = max(res, dfs(i, k) + leftsum, dfs(k + 1, j) + rightsum) memo[i][j] = res return res return dfs(0, n - 1) #%% s = Solution() stoneValue = [6,2,3,4,5,5] print(s.stoneGameV(stoneValue)) stoneValue = [7,7,7,7,7,7,7] print(s.stoneGameV(stoneValue))
输出：
18
28
3. 石子游戏 Stone Game VI
Alice 和 Bob 轮流玩一个游戏，Alice 先手。
一堆石子里总共有 n 个石子，轮到某个玩家时，他可以 移出 一个石子并得到这个石子的价值。Alice 和 Bob 对石子价值有 不一样的的评判标准 。双方都知道对方的评判标准。
给你两个长度为 n 的整数数组 aliceValues 和 bobValues 。aliceValues[i] 和 bobValues[i] 分别表示 Alice 和 Bob 认为第 i 个石子的价值。
所有石子都被取完后，得分较高的人为胜者。如果两个玩家得分相同，那么为平局。两位玩家都会采用 最优策略 进行游戏。
请你推断游戏的结果，用如下的方式表示：
如果 Alice 赢，返回 1 。
如果 Bob 赢，返回 -1 。
如果游戏平局，返回 0 。
示例 1：
输入：aliceValues = [1,3], bobValues = [2,1]
输出：1
解释：
如果 Alice 拿石子 1 （下标从 0开始），那么 Alice 可以得到 3 分。
Bob 只能选择石子 0 ，得到 2 分。
Alice 获胜。
示例 2：
输入：aliceValues = [1,2], bobValues = [3,1]
输出：0
解释：
Alice 拿石子 0 ， Bob 拿石子 1 ，他们得分都为 1 分。
打平。
示例 3：
输入：aliceValues = [2,4,3], bobValues = [1,6,7]
输出：-1
解释：
不管 Alice 怎么操作，Bob 都可以得到比 Alice 更高的得分。
比方说，Alice 拿石子 1 ，Bob 拿石子 2 ， Alice 拿石子 0 ，Alice 会得到 6 分而 Bob 得分为 7 分。
Bob 会获胜。
提示：
n == aliceValues.length == bobValues.length
1 <= n <= 105
1 <= aliceValues[i], bobValues[i] <= 100
代码1： 动态规划
from typing import List class Solution: def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int: n = len(aliceValues) total_values = [(aliceValues[i] + bobValues[i], i) for i in range(n)] total_values.sort(reverse=True) alice_dp, bob_dp = [0] * (n + 1), [0] * (n + 1) for i in range(n): if i % 2 == 0: alice_dp[i // 2 + 1] = alice_dp[i // 2] + aliceValues[total_values[i][1]] else: bob_dp[i // 2 + 1] = bob_dp[i // 2] + bobValues[total_values[i][1]] for i in range(n // 2): alice_dp[i + 1] = max(alice_dp[i], alice_dp[i + 1]) bob_dp[i + 1] = max(bob_dp[i], bob_dp[i + 1]) diff = alice_dp[n // 2] - bob_dp[n // 2] if diff > 0: return 1 elif diff < 0: return -1 else: return 0 #%% s = Solution() aliceValues = [1,3] bobValues = [2,1] print(s.stoneGameVI(aliceValues, bobValues)) aliceValues = [1,2] bobValues = [3,1] print(s.stoneGameVI(aliceValues, bobValues)) aliceValues = [2,4,3] bobValues = [1,6,7] print(s.stoneGameVI(aliceValues, bobValues))
代码2： 贪心算法
from typing import List class Solution: def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int: n = len(aliceValues) stones = [(aliceValues[i] + bobValues[i], i) for i in range(n)] stones.sort(reverse=True) a_score, b_score = 0, 0 for i in range(n): if i % 2 == 0: a_score += aliceValues[stones[i][1]] else: b_score += bobValues[stones[i][1]] if a_score > b_score: return 1 elif a_score < b_score: return -1 else: return 0 #%% s = Solution() aliceValues = [1,3] bobValues = [2,1] print(s.stoneGameVI(aliceValues, bobValues)) aliceValues = [1,2] bobValues = [3,1] print(s.stoneGameVI(aliceValues, bobValues)) aliceValues = [2,4,3] bobValues = [1,6,7] print(s.stoneGameVI(aliceValues, bobValues))
输出：
1
0
-1
