1. 石子游戏 Stone Game VII

石子游戏中，爱丽丝和鲍勃轮流进行自己的回合，爱丽丝先开始 。

有 n 块石子排成一排。每个玩家的回合中，可以从行中 移除 最左边的石头或最右边的石头，并获得与该行中剩余石头值之 和 相等的得分。当没有石头可移除时，得分较高者获胜。

鲍勃发现他总是输掉游戏（可怜的鲍勃，他总是输），所以他决定尽力 减小得分的差值 。爱丽丝的目标是最大限度地 扩大得分的差值 。

给你一个整数数组 stones ，其中 stones[i] 表示 从左边开始 的第 i 个石头的值，如果爱丽丝和鲍勃都 发挥出最佳水平 ，请返回他们 得分的差值 。

示例 1：

输入：stones = [5,3,1,4,2]

输出：6

解释：

- 爱丽丝移除 2 ，得分 5 + 3 + 1 + 4 = 13 。游戏情况：爱丽丝 = 13 ，鲍勃 = 0 ，石子 = [5,3,1,4] 。

- 鲍勃移除 5 ，得分 3 + 1 + 4 = 8 。游戏情况：爱丽丝 = 13 ，鲍勃 = 8 ，石子 = [3,1,4] 。

- 爱丽丝移除 3 ，得分 1 + 4 = 5 。游戏情况：爱丽丝 = 18 ，鲍勃 = 8 ，石子 = [1,4] 。

- 鲍勃移除 1 ，得分 4 。游戏情况：爱丽丝 = 18 ，鲍勃 = 12 ，石子 = [4] 。

- 爱丽丝移除 4 ，得分 0 。游戏情况：爱丽丝 = 18 ，鲍勃 = 12 ，石子 = [] 。

得分的差值 18 - 12 = 6 。

示例 2：

输入：stones = [7,90,5,1,100,10,10,2]

输出：122

提示：

   n == stones.length

   2 <= n <= 1000

   1 <= stones[i] <= 1000

代码1： 动态规划

from typing import List
class Solution:
    def stoneGameVII(self, stones: List[int]) -> int:
        n = len(stones)
        dp = [[0] * n for _ in range(n)]
        prefix_sum = [0] * (n + 1)
        for i in range(n):
            prefix_sum[i + 1] = prefix_sum[i] + stones[i]
        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                dp[i][j] = max(prefix_sum[j + 1] - prefix_sum[i + 1] - dp[i + 1][j], 
                               prefix_sum[j] - prefix_sum[i] - dp[i][j - 1])
        return dp[0][n - 1]
#%%
s = Solution()
stones = [5,3,1,4,2]
print(s.stoneGameVII(stones))
stones = [7,90,5,1,100,10,10,2]
print(s.stoneGameVII(stones))

代码2：记忆化搜索

from typing import List
class Solution:
    def stoneGameVII(self, stones: List[int]) -> int:
        n = len(stones)
        prefix_sum = [0] * (n + 1)
        for i in range(n):
            prefix_sum[i + 1] = prefix_sum[i] + stones[i]
        memo = [[None] * n for _ in range(n)]
        def dfs(left, right):
            if left == right:
                return 0
            if memo[left][right] is not None:
                return memo[left][right]
            res = max(prefix_sum[right + 1] - prefix_sum[left + 1] - dfs(left + 1, right), 
                      prefix_sum[right] - prefix_sum[left] - dfs(left, right - 1))
            memo[left][right] = res
            return res
        return dfs(0, n - 1)
#%%
s = Solution()
stones = [5,3,1,4,2]
print(s.stoneGameVII(stones))
stones = [7,90,5,1,100,10,10,2]
print(s.stoneGameVII(stones))

输出：

6

122

2. 石子游戏 Stone Game VIII

Alice 和 Bob 玩一个游戏，两人轮流操作， Alice 先手 。

总共有 n 个石子排成一行。轮到某个玩家的回合时，如果石子的数目 大于 1 ，他将执行以下操作：

   选择一个整数 x > 1 ，并且 移除 最左边的 x 个石子。

   将 移除 的石子价值之 和 累加到该玩家的分数中。

   将一个 新的石子 放在最左边，且新石子的值为被移除石子值之和。

当只剩下 一个 石子时，游戏结束。

Alice 和 Bob 的 分数之差 为 (Alice 的分数 - Bob 的分数) 。 Alice 的目标是 最大化 分数差，Bob 的目标是 最小化 分数差。

给你一个长度为 n 的整数数组 stones ，其中 stones[i] 是 从左边起 第 i 个石子的价值。请你返回在双方都采用 最优 策略的情况下，Alice 和 Bob 的 分数之差 。

示例 1：

输入：stones = [-1,2,-3,4,-5]

输出：5

解释：

- Alice 移除最左边的 4 个石子，得分增加 (-1) + 2 + (-3) + 4 = 2 ，并且将一个价值为 2 的石子放在最左边。stones = [2,-5] 。

- Bob 移除最左边的 2 个石子，得分增加 2 + (-5) = -3 ，并且将一个价值为 -3 的石子放在最左边。stones = [-3] 。

两者分数之差为 2 - (-3) = 5 。

示例 2：

输入：stones = [7,-6,5,10,5,-2,-6]

输出：13

解释：

- Alice 移除所有石子，得分增加 7 + (-6) + 5 + 10 + 5 + (-2) + (-6) = 13 ，并且将一个价值为 13 的石子放在最左边。stones = [13] 。

两者分数之差为 13 - 0 = 13 。

示例 3：

输入：stones = [-10,-12]

输出：-22

解释：

- Alice 只有一种操作，就是移除所有石子。得分增加 (-10) + (-12) = -22 ，并且将一个价值为 -22 的石子放在最左边。stones = [-22] 。

两者分数之差为 (-22) - 0 = -22 。

提示：

   n == stones.length

   2 <= n <= 10^5

   -10^4 <= stones[i] <= 10^4

代码： 动态规划

from typing import List
class Solution:
    def stoneGameVIII(self, stones: List[int]) -> int:
        n = len(stones)
        prefix_sum = [0] * (n + 1)
        for i in range(n):
            prefix_sum[i + 1] = prefix_sum[i] + stones[i]
        dp = [0] * n
        dp[n - 1] = prefix_sum[n]
        for i in range(n - 2, 0, -1):
            dp[i] = max(dp[i + 1], prefix_sum[i + 1] - dp[i + 1])
        return dp[1]
#%%
s = Solution()
stones = [-1,2,-3,4,-5]
print(s.stoneGameVIII(stones))
stones = [7,-6,5,10,5,-2,-6]
print(s.stoneGameVIII(stones))
stones = [-10,-12]
print(s.stoneGameVIII(stones))

输出：

5

13

-22

3. 石子游戏 Stone Game IX

Alice 和 Bob 再次设计了一款新的石子游戏。现有一行 n 个石子，每个石子都有一个关联的数字表示它的价值。给你一个整数数组 stones ，其中 stones[i] 是第 i 个石子的价值。

Alice 和 Bob 轮流进行自己的回合，Alice 先手。每一回合，玩家需要从 stones 中移除任一石子。

   如果玩家移除石子后，导致 所有已移除石子 的价值 总和 可以被 3 整除，那么该玩家就 输掉游戏 。

   如果不满足上一条，且移除后没有任何剩余的石子，那么 Bob 将会直接获胜（即便是在 Alice 的回合）。

假设两位玩家均采用 最佳 决策。如果 Alice 获胜，返回 true ；如果 Bob 获胜，返回 false 。

示例 1：

输入：stones = [2,1]

输出：true

解释：游戏进行如下：

- 回合 1：Alice 可以移除任意一个石子。

- 回合 2：Bob 移除剩下的石子。  

已移除的石子的值总和为 1 + 2 = 3 且可以被 3 整除。因此，Bob 输，Alice 获胜。

示例 2：

输入：stones = [2]

输出：false

解释：Alice 会移除唯一一个石子，已移除石子的值总和为 2 。  

由于所有石子都已移除，且值总和无法被 3 整除，Bob 获胜。

示例 3：

输入：stones = [5,1,2,4,3]

输出：false

解释：Bob 总会获胜。其中一种可能的游戏进行方式如下：

- 回合 1：Alice 可以移除值为 1 的第 2 个石子。已移除石子值总和为 1 。

- 回合 2：Bob 可以移除值为 3 的第 5 个石子。已移除石子值总和为 = 1 + 3 = 4 。

- 回合 3：Alices 可以移除值为 4 的第 4 个石子。已移除石子值总和为 = 1 + 3 + 4 = 8 。

- 回合 4：Bob 可以移除值为 2 的第 3 个石子。已移除石子值总和为 = 1 + 3 + 4 + 2 = 10.

- 回合 5：Alice 可以移除值为 5 的第 1 个石子。已移除石子值总和为 = 1 + 3 + 4 + 2 + 5 = 15.

Alice 输掉游戏，因为已移除石子值总和（15）可以被 3 整除，Bob 获胜。

提示：

   1 <= stones.length <= 10^5

   1 <= stones[i] <= 10^4

代码：

from typing import List
class Solution:
    def stoneGameIX(self, stones: List[int]) -> bool:
        count = [0] * 3  # 统计每个余数出现的次数
        for stone in stones:
            count[stone % 3] += 1
        if count[0] % 2 == 0:  # 如果余数为 0 的石子个数为偶数，Alice 一定会输
            return count[1] > 0 and count[2] > 0  # 只有同时存在余数为 1 和余数为 2 的石子，Bob 才能获胜
        return abs(count[1] - count[2]) > 2  # 如果余数为 0 的石子个数为奇数，Alice 一定会获胜
#%%
s = Solution()
stones = [2,1]
print(s.stoneGameIX(stones))
stones = [2]
print(s.stoneGameIX(stones))
stones = [5,1,2,4,3]
print(s.stoneGameIX(stones))

输出：

True

False

False