LeetCode 1872 石子游戏 VIII TypeScript 实现
题目大意
给定数组 stones ，两人轮流进行操作：
- 每次选择至少前 k 个石子（k≥2）
- 拿走前 k 个石子，得分 = 前 k 个石子总和
- 拿走后，后面石子向前拼接，继续游戏
- 两人都最优策略，先手尽可能最大化分差，后手尽可能最小化分差
求先手与后手的最终分差
核心思路（逆向DP）
设：
- dp[i] ：从下标 i 开始剩余石子，当前玩家能拿到的最大分差
- 前缀和 preSum[i] ：前 i 个石子总和
状态转移：
1. 从后往前遍历
2. 当前玩家两种选择：- 直接拿前 i+1 个（≥2），收益 preSum[i+1] - dp[i+1]
- 不拿，继承后面最优 dp[i+1]
3. 取最大值： dp[i] = max(preSum[i+1] - dp[i+1], dp[i+1])
答案： dp[1] （至少拿2个，从下标1开始）
TypeScript 代码实现
typescript
function stoneGameVIII(stones: number[]): number {
const n = stones.length;
// 前缀和 preSum[0]=0, preSum[1]=stones[0], preSum[2]=stones[0]+stones[1]...
const preSum: number[] = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) {
preSum[i + 1] = preSum[i] + stones[i];
}
// dp[i] 表示从i位置开始，当前玩家最大分差
const dp: number[] = new Array(n).fill(0);
dp[n - 1] = preSum[n];
// 逆序遍历
for (let i = n - 2; i >= 1; i--) {
dp[i] = Math.max(preSum[i + 1] - dp[i + 1], dp[i + 1]);
}
return dp[1];
}
// 测试用例
console.log(stoneGameVIII([-1,2,-3,4,-5])); // 4
console.log(stoneGameVIII([7,-6,5,10,5,-2,-6])); // 13
console.log(stoneGameVIII([-10,-12])); // -22
空间优化（一维压缩 O(1)）
不需要完整 dp 数组，只用一个变量记录后一项即可：
typescript
function stoneGameVIII(stones: number[]): number {
const n = stones.length;
let preSum = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) {
preSum[i + 1] = preSum[i] + stones[i];
}
let nextDp = preSum[n];
for (let i = n - 2; i >= 1; i--) {
nextDp = Math.max(preSum[i + 1] - nextDp, nextDp);
}
return nextDp;
}
复杂度
- 时间：O(n)
- 空间：O(n)（前缀和），优化后可再压缩前缀和到 O(1) 边算边推
需要我给你推导一遍DP状态转移的博弈论逻辑，或者手写一遍递归+记忆化版本吗？
