题目描述
Alice 和 Bob 玩一个游戏,两人轮流操作,Alice 先手。
总共有 n
个石子排成一行。轮到某个玩家的回合时,如果石子的数目 大于 1,他将执行以下操作:
- 选择一个整数
x > 1
,并且 移除 最左边的x
个石子。 - 将 移除 的石子价值之 和 累加到该玩家的分数中。
- 将一个 新的石子 放在最左边,且新石子的值为被移除石子值之和。
当只剩下 一个 石子时,游戏结束。
Alice 和 Bob 的 分数之差 为 (Alice 的分数 - Bob 的分数)
。Alice 的目标是 最大化 分数差,Bob 的目标是 最小化 分数差。
给你一个长度为 n
的整数数组 stones
,其中 stones[i]
是 从左边起 第 i
个石子的价值。请你返回在双方都采用 最优 策略的情况下,Alice 和 Bob 的 分数之差。
样例
输入: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 。
输入:stones = [7,-6,5,10,5,-2,-6]
输出:13
解释:
- Alice 移除所有石子,得分增加 7 + (-6) + 5 + 10 + 5 + (-2) + (-6) = 13,
并且将一个价值为 13 的石子放在最左边。
stones = [13]。
两者分数之差为 13 - 0 = 13。
输入: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
算法
(动态规划) $O(n)$
- 设状态 $f(i)$ 表示还剩下 $i$ 堆石子时,先手与后手的最大分数差。$i$ 的范围为 $1$ 到 $n$。
- 初始时,$f(1) = 0$,其余待定。
- 转移时,枚举本次先手拿完后剩余的石子数量 $j$,其中 $1 \le j \le i - 1$,转移 $f(i) = \min(f(i), sum(n - j) - f(j))$。其中 $sum(n - j + 1)$ 表示 $n - j + 1$ 的前缀和,这个收益计算是因为每一次拿完后都会新增一个等于前缀和的石子放在最前边。
- 最终答案为 $f(n)$。
- 由于枚举 $j$ 会导致转移时间为 $O(n)$,所以考虑使用额外变量 $g$ 来表示 $\max(sum(n - i) - f(i))$,每次转移只需要令 $f(i) = g$,然后更新 $g$ 即可。
- 进一步发现,可以去掉数组,每次只需要更新 $f = g$,且 $g = \max(g, sum - f)$。
时间复杂度
- 共 $O(n)$ 个状态,每次转移时间为常数,故总时间复杂度为 $O(n)$。
空间复杂度
- 空间优化后,仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int stoneGameVIII(vector<int>& stones) {
const int n = stones.size();
int sum = 0;
for (int i = 0; i < n; i++)
sum += stones[i];
int f = 0, g = sum;
for (int i = 1; i < n; i++) {
f = g;
sum -= stones[n - i];
g = max(g, sum - f);
}
return f;
}
};