石子游戏 III

标签: 数组数学动态规划博弈

难度: Hard

Alice 和 Bob 继续他们的石子游戏。几堆石子 排成一行 ，每堆石子都对应一个得分，由数组 stoneValue 给出。

Alice 和 Bob 轮流取石子，Alice 总是先开始。在每个玩家的回合中，该玩家可以拿走剩下石子中的的前 1、2 或 3 堆石子 。比赛一直持续到所有石头都被拿走。

每个玩家的最终得分为他所拿到的每堆石子的对应得分之和。每个玩家的初始分数都是 0 。

比赛的目标是决出最高分，得分最高的选手将会赢得比赛，比赛也可能会出现平局。

假设 Alice 和 Bob 都采取 最优策略 。

如果 Alice 赢了就返回 "Alice" ，Bob 赢了就返回 "Bob"，分数相同返回 "Tie" 。

示例 1：

输入：values = [1,2,3,7]
输出："Bob"
解释：Alice 总是会输，她的最佳选择是拿走前三堆，得分变成 6 。但是 Bob 的得分为 7，Bob 获胜。

示例 2：

输入：values = [1,2,3,-9]
输出："Alice"
解释：Alice 要想获胜就必须在第一个回合拿走前三堆石子，给 Bob 留下负分。
如果 Alice 只拿走第一堆，那么她的得分为 1，接下来 Bob 拿走第二、三堆，得分为 5 。之后 Alice 只能拿到分数 -9 的石子堆，输掉比赛。
如果 Alice 拿走前两堆，那么她的得分为 3，接下来 Bob 拿走第三堆，得分为 3 。之后 Alice 只能拿到分数 -9 的石子堆，同样会输掉比赛。
注意，他们都应该采取 最优策略 ，所以在这里 Alice 将选择能够使她获胜的方案。

示例 3：

输入：values = [1,2,3,6]
输出："Tie"
解释：Alice 无法赢得比赛。如果她决定选择前三堆，她可以以平局结束比赛，否则她就会输。

提示：

1 <= stoneValue.length <= 5 * 10⁴
-1000 <= stoneValue[i] <= 1000

Submission

运行时间: 279 ms

内存: 19.7 MB

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        s, n = 0, len(stoneValue)
        dp = [0] * 3
        for i in range(n-1, -1, -1):
            s += stoneValue[i]
            ans = s-min(dp)
            dp = [ans, dp[0], dp[1]]
            # print(dp)
        if dp[0] > s-dp[0]:
            return "Alice"
        elif dp[0] == s-dp[0]:
            return "Tie"
        else:
            return "Bob"

Explain

该题解采用动态规划的思路。定义dp[i]为从第i个石子开始到最后一个石子结束时，当前玩家与对手的分数差的最大值。从后向前计算dp数组，每次计算考虑取1, 2, 或3堆石子的情况，选择能使当前分数最大化的方案。dp数组使用滚动数组优化空间复杂度，最终比较dp[0]与对手的分数差，以判断赢家。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        s, n = 0, len(stoneValue)
        dp = [0] * 3  # 初始化滚动数组
        for i in range(n-1, -1, -1):  # 从后向前计算每个位置的最优解
            s += stoneValue[i]  # 累计从i到末尾的石子总分
            ans = s - min(dp)  # 计算当前位置的最优分数差
            dp = [ans, dp[0], dp[1]]  # 更新滚动数组
        if dp[0] > s - dp[0]:  # 若Alice分数较高
            return "Alice"
        elif dp[0] == s - dp[0]:  # 若分数相等
            return "Tie"
        else:  # 若Bob分数较高
            return "Bob"

Explore

动态规划的核心在于每个玩家都假设对方会采取对自己最不利的策略。在计算dp[i]时，我们假设从i开始，当前玩家选择了最优的策略，即尽可能增加自己的得分并减少对手的得分。dp[i]计算反映的是在玩家和对手都采取最优策略时的得分差。因此，每个dp[i]的计算都是基于对手对其后续选择的最优反应，这样通过逐步递推，确保了两个玩家都在采取最优策略。

在这个问题中，s表示从当前石子i到最后一个石子的总分。min(dp)表示在当前玩家取了一定数量石子后，对手面对的三种情况中最小的分数差。这样，s - min(dp)实际上是计算在对手面对最坏情况下，当前玩家能够获得的最大分数差。转移方程中的min(dp)代表的是对手面对最优选择时的情况，确保当前玩家考虑到对手也会采取最优策略。

在Python中，整数类型是动态的，可以扩展到很大的数值而不会发生传统意义上的溢出。因此，在累加过程中不会导致数值溢出错误。此外，这种比较方法是数学上正确的，因为它直接比较了当前玩家和对手的分数差。只要分数的计算正确，这种方法就能正确反映谁是获胜者。

这个问题的设定可能来源于游戏规则的限制，通常在类似的石子游戏中，每次只允许玩家从连续的堆中取走一定数量的石子，并且这个数量有上限。如果题目规定了每次最多取3堆，那么动态规划的状态转移只需要考虑这三种情况。这是基于题目设定的限制，并不是算法本身的限制。如果游戏规则允许取更多堆，那么状态转移方程将需要相应调整以包含更多的情况。