1872-石子游戏 VIII

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:26 2023-09-13 16:06:26 Updated    

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

方法一：动态规划

提示 1

在任意一名玩家进行操作之后，剩余的所有石子的价值总和不会发生变化。

对于每一步操作，玩家可以把「最左侧」的 x 枚石子进行「价值合并」，并获得与「价值」等价的分数。因此，最左侧的石子的价值一定是 stones 的某一个前缀和，即玩家在每一轮获得的分数一定是初始数组 stones 的某一个前缀和。

提示 2

根据提示 1，我们可以将题目中的游戏转化成如下等价的形式：

  • 我们求出 stones 的前缀和数组 pre，其中：

    \textit{pre}[i] = \sum_{j=0}^i \textit{stones}[j]

  • Alice 和 Bob 依次在数组 pre 上进行操作，并且 Alice 先手。在一次操作中，当前玩家可以选择一个下标 u，获得 pre}[u] 的分数：

    • 如果当前玩家是 Alice 并且是首次操作，那么 u 不能为 0。对应到题目中的游戏规则，即为「选择的石子数量 x 必须大于 1」；

    • 对于其余的情况，如果对手的上一次操作选择的下标是 v，那么必须有 u > v。对应到题目中的游戏规则，即为「对手上一次操作合并了若干枚石子，使得最左侧的石子的价值为 pre}[v]」，同时「当前玩家合并了从最左侧的石子开始，到原本在数组 stones 中下标为 u 的石子为止的所有石子，使得最左侧的石子的价值为 pre}[u]」。

  • 设数组 stones 和 pre 的长度为 n。如果当前玩家选择了下标 n-1，那么它就会合并剩余的所有石子，游戏结束。

思路与算法

我们可以使用基于博弈思想的动态规划解决提示 2 中的游戏。

设 f(i) 表示当 Alice 可以选择的下标 u 在 [i, n) 范围内时，Alice 与 Bob 分数的最大差值。在进行状态转移时，我们可以考虑 Alice 是否选择了 i 作为下标 u；

  • 如果 Alice 没有选择 i 作为下标 u，那么她需要在 [i+1, n) 的范围内进行选择，因此有状态转移方程：

    f[i] = f[i+1]

  • 如果 Alice 选择了 i 作为下标 u，那么她获得了 pre}[i] 的分数，并且轮到 Bob 在剩余的范围 [i+1, n) 中进行选择。由于 Bob 会采用最优策略，因此在 [i+1, n) 的范围内，Bob 与 Alice 分数的最大差值就为 f[i+1]，因此有状态转移方程：

    f[i] = \textit{pre}[i] - f[i+1]

由于 Alice 会采用最优策略，因此状态转移选择二者中的较大值：

f[i] = \max ( f[i+1], \textit{pre}[i] - f[i+1] )

我们从 i=n-1 开始倒序地计算所有的状态，最终的答案即为 f[1]。

细节

当 i=n-1 时，f[i+1] 不是一个合法的状态，因此我们可以将此时的 i 作为边界情况进行考虑，即：

f[i] = \textit{pre}[i]

然后从 i=n-2 开始倒序计算所有的状态即可。

思考

为什么最终的答案是 f[1] 而不是 f[0]？

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int stoneGameVIII(vector<int>& stones) {
        int n = stones.size();
        vector<int> pre;
        partial_sum(stones.begin(), stones.end(), back_inserter(pre));
        vector<int> f(n);
        f[n - 1] = pre[n - 1];
        for (int i = n - 2; i >= 1; --i) {
            f[i] = max(f[i + 1], pre[i] - f[i + 1]);
        }
        return f[1];
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
class Solution:
    def stoneGameVIII(self, stones: List[int]) -> int:
        n = len(stones)
        pre = list(accumulate(stones))
        f = [0] * n
        f[n - 1] = pre[n - 1]
        for i in range(n - 2, 0, -1):
            f[i] = max(f[i + 1], pre[i] - f[i + 1])
        return f[1]

复杂度分析

  • 时间复杂度：O(n)。

  • 空间复杂度：O(n)，即为数组 pre 和 f 需要的空间。

 Comments
On this page
1872-石子游戏 VIII