LeetCode 1563. 石子游戏 V
目录
题目描述
题意分析
一排石子摆在桌上，每轮 Alice 把当前这排石子从某处切成左右两段，Bob 计算两段的和，把和更大的那段扔掉，Alice 得到被保留那段的分数；如果两段和相等，则由 Alice 自己决定扔掉哪一段。重复这个过程直到只剩一颗石子，游戏结束。求 Alice 能拿到的最高总分。
尽管出现了两个人，这不是对抗博弈：Bob 的行为完全由规则决定（永远扔大的），没有任何选择权；只有在两段和相等时决定权才回到 Alice 手上。所以本质是 Alice 一个人在做决策链的最优化。
「切一刀后只保留一段，继续在这一段上切」这个形态说明子问题永远是原数组的一个连续区间，而且切割点把区间劈成两个更短的区间。区间是被完整保留下来的、不会跳跃，这直接指向以区间为状态的动态规划。
石子数上限是 500。这个数字很关键：$n^3 = 1.25 \times 10^8$ 是可以接受的，而 $n^2$ 显得过于宽松，所以出题人预期的正是三重循环的区间动规——枚举长度、左端点、切割点。
石子值都是正整数（上界 $10^6$），所以区间和严格随区间变长而增大，不存在零和负数带来的退化情况。总和最多 $5 \times 10^8$，
int装得下。边界上，区间只剩一颗石子时游戏结束，Alice 再也拿不到分，这个状态的值是 0。
解法：区间动态规划
核心思路
每次切割后只保留连续的一侧，子问题仍是原数组的一个区间，因此使用区间 DP。
定义
dp[left][right]：当前只剩闭区间[left,right]时，Alice 从现在开始最多还能获得的分数。单元素区间无法再切，边界为dp[i][i]=0。枚举切割点
split，左段是[left,split]，右段是[split+1,right]：
- 左段和不大于右段和时，Alice 可以保留左段，收益为
leftSum + dp[left][split]；- 右段和不大于左段和时，Alice 可以保留右段，收益为
rightSum + dp[split+1][right]。两个判断必须分别写成
<=和>=。两段和不等时只有较小侧合法；相等时两个条件同时成立，恰好枚举 Alice 的两种选择。对所有切割点和合法保留侧取最大值。状态不变量：按区间长度递增计算时，处理
dp[left][right]前，所有严格更短区间的最优值已经确定。 每个转移只依赖左右两个更短区间，因此由长度归纳，当前状态枚举了第一刀后的全部合法选择并接上最优子问题，结果正确。用前缀和在 $O(1)$ 时间计算任意区间和，否则三重循环内部再次求和会退化为 $O(n^4)$。
解题步骤
- 构造前缀和
prefix，区间[l,r]的和为prefix[r+1]-prefix[l]。- 创建
dp[n][n]，单元素状态保持 0。- 区间长度从 2 增加到
n。- 对每个区间枚举
split从left到right-1，保证左右两段都非空。- 分别按
leftSum<=rightSum、leftSum>=rightSum更新答案。- 返回
dp[0][n-1]。样例
[6,2,3,4,5,5]的最优值为 18。边界[7]没有合法切割，答案为 0；区间[5,5]两侧和相等，两种保留方向都会被检查。
代码实现
class Solution {
public int stoneGameV(int[] stoneValue) {
int n = stoneValue.length;
int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++) {
prefix[i + 1] = prefix[i] + stoneValue[i];
}
int[][] dp = new int[n][n];
for (int length = 2; length <= n; length++) {
for (int left = 0; left + length <= n; left++) {
int right = left + length - 1;
for (int split = left; split < right; split++) {
int leftSum = prefix[split + 1] - prefix[left];
int rightSum = prefix[right + 1] - prefix[split + 1];
if (leftSum <= rightSum) {
dp[left][right] = Math.max(
dp[left][right], leftSum + dp[left][split]);
}
if (leftSum >= rightSum) {
dp[left][right] = Math.max(
dp[left][right], rightSum + dp[split + 1][right]);
}
}
}
}
return dp[0][n - 1];
}
}
func stoneGameV(stoneValue []int) int {
n := len(stoneValue)
prefix := make([]int, n+1)
for i, value := range stoneValue {
prefix[i+1] = prefix[i] + value
}
dp := make([][]int, n)
for i := range dp {
dp[i] = make([]int, n)
}
for length := 2; length <= n; length++ {
for left := 0; left+length <= n; left++ {
right := left + length - 1
for split := left; split < right; split++ {
leftSum := prefix[split+1] - prefix[left]
rightSum := prefix[right+1] - prefix[split+1]
if leftSum <= rightSum {
dp[left][right] = maxInt(
dp[left][right], leftSum+dp[left][split])
}
if leftSum >= rightSum {
dp[left][right] = maxInt(
dp[left][right], rightSum+dp[split+1][right])
}
}
}
}
return dp[0][n-1]
}
func maxInt(a int, b int) int {
if a > b {
return a
}
return b
}
复杂度分析
- 时间复杂度： $O(n^3)$。共有 $O(n^2)$ 个区间，每个区间枚举 $O(n)$ 个切割点。
- 空间复杂度： $O(n^2)$，用于状态表；前缀和占 $O(n)$。
关键点总结
- “切一刀后只保留一侧”使状态始终是连续区间，是区间 DP 的直接信号。
dp[left][right]只表示从当前区间开始的后续最优分数，不包含此前得分。- 按长度递增保证所有转移依赖的子区间已经计算。
- 切割点范围必须是
[left,right-1]，左右两段都不能空。- 相等时 Alice 可选任一侧，两条非严格不等式必须同时执行。
- 前缀和让最内层的区间求和保持常数时间。
易错点总结
- 相等时只保留固定一侧： 两侧后续收益可能不同，必须取两种选择的最大值。
- 切割点取到
right： 右段为空，会访问非法状态。- 右段从
split开始： 会与左段重复包含切割位置；正确起点是split+1。- 不按区间长度计算： 可能读取尚未完成的子状态 0。
- 单元素状态设为石子值： 单颗石子无法继续切割，后续得分应为 0。
- 最内层重新遍历求区间和： 时间复杂度会从 $O(n^3)$ 退化到 $O(n^4)$。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 1690. 石子游戏 VII | 中等 | 真正的双人对抗，状态存分差且转移取极小化极大，与本题的单方最优不同 |
| 877. 石子游戏 | 中等 | 只从两端取石子，区间状态仅有两种转移，还有先手必胜的数学结论 |
| 486. 预测赢家 | 中等 | 同为两端取数的分差动规，但要判断先手是否不败而非求最高分 |
| 312. 戳气球 | 困难 | 枚举的是「最后戳破的那个」而不是切割点，需要逆向思考区间边界 |
| 1000. 合并石头的最低成本 | 困难 | 每次合并 K 堆，状态要多一维记录当前段数，切割点还需按步长跳跃 |
| 516. 最长回文子序列 | 中等 | 转移只看两端字符是否相等，不需要枚举切割点，是区间动规的最简形态 |
| 241. 为运算表达式设计优先级 | 中等 | 同样枚举分割点合并左右结果，但返回的是全部可能值而非最优值 |
| 87. 扰乱字符串 | 困难 | 分割点两侧还要考虑是否交换，状态需要额外一维表示长度 |