石子游戏 VIII

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

难度: Hard

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

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

  1. 选择一个整数 x > 1 ，并且 移除 最左边的 x 个石子。
  2. 将 移除 的石子价值之 和 累加到该玩家的分数中。
  3. 将一个 新的石子 放在最左边，且新石子的值为被移除石子值之和。

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

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 <= 105
  • -104 <= stones[i] <= 104

Submission

运行时间: 131 ms

内存: 27.4 MB

class Solution:
    def stoneGameVIII(self, stones: List[int]) -> int:            

        n = len(stones)
        for i in range(1, n):
            stones[i] += stones[i-1]

        #dp = [0] * n

        curmax = stones[-1]
        #dp[-1] = stones[-1]

        for j in range(n-2, 0, -1):
            profit = stones[j] - curmax
            if profit > curmax:
                curmax = profit
        
        return curmax

Explain

这道题解的思路是动态规划。首先，通过累加前缀和，将stones数组转换为存储从第一个石头到当前位置所有石头的总和。接着，从数组末尾向前遍历，计算每个位置可以给后手带来的最小分差。具体来说，对于每个位置j，计算当Alice到达该位置时，如果接下来由Bob开始，他们分数差的最优解。这是通过取当前位置的前缀和减去之前位置得到的最大收益来计算的。通过这种方式，递推得到最终的结果。

时间复杂度: O(n)

空间复杂度: O(1)

# Solution class containing the method to solve the problem

class Solution:
    def stoneGameVIII(self, stones: List[int]) -> int:
        n = len(stones)
        # Compute the prefix sums in place
        for i in range(1, n):
            stones[i] += stones[i-1]
        # Initialize the current maximum score difference that Alice can secure
        curmax = stones[-1]
        # Dynamic programming to determine the maximum score difference
        for j in range(n-2, 0, -1):
            profit = stones[j] - curmax
            # Update curmax if the current profit leads to a better outcome for Alice
            if profit > curmax:
                curmax = profit
        # Return the maximum score difference Alice can secure
        return curmax

Explore

前缀和数组在这个问题中的作用主要是为了快速计算从数组的任意起始位置到任意结束位置的石头总和。通过前缀和，我们可以在常数时间内得到任意区间的石子总数，这是动态规划状态转移的基础。在这道题中，前缀和数组的使用使得我们能够快速计算出在某个位置j选择停止后，Alice与Bob之间的得分差。这种快速计算区间和的能力极大地简化了问题的复杂性，使得我们能够专注于动态规划的状态转移逻辑。

动态规划的核心在于维护一个变量 `curmax`，这个变量表示Alice可以确保的最大分差。对于每个位置j，我们计算 `profit = stones[j] - curmax`。这里，`stones[j]` 是Alice在位置j停止后可以获得的总分数，而`curmax`是到目前为止Bob可以通过最优选择获得的最大分数的负值。如果`profit`大于`curmax`，则更新`curmax`为`profit`。这样的转移方程确保了每一步都考虑了使Alice分数最大化的可能性，从而找到最终的最优解。

从数组末尾向前遍历的原因是这样可以更自然地模拟游戏的决策过程。在这个问题中，Alice和Bob在做出决策时，总是考虑当前位置和之前的最优决策结果。从后向前遍历可以让我们在确定当前位置的最优决策时，已经知道所有后续位置的最优结果，这符合动态规划“由后向前”的特性。此外，这种遍历方式也是因为题目的游戏规则导致的，即Alice选择停止的位置越往前，她能够确保的优势越大，因此我们需要从后往前评估每个位置的价值。

这样的更新逻辑确保了在每个位置j，如果选择停止可以获得比之前任何位置更大的分差，则更新`curmax`。这意味着`curmax`总是保持为Alice可以通过最优策略达到的最大分差。这种方法是贪心策略的一种体现——在每一步都尝试取得当前可获得的最大利益。通过这种方式，我们可以确保在遍历结束时，`curmax`存储的是Alice在所有可能的停止位置中，能够确保的最大分差，从而达到全局最优。