豆包 LeetCode 1872.石子游戏 VIII TypeScript实现

LeetCode 1872 石子游戏 VIII TypeScript 实现题目大意给定数组 stones 两人轮流进行操作- 每次选择至少前 k 个石子k≥2- 拿走前 k 个石子得分 前 k 个石子总和- 拿走后后面石子向前拼接继续游戏- 两人都最优策略先手尽可能最大化分差后手尽可能最小化分差求先手与后手的最终分差核心思路逆向DP设- dp[i] 从下标 i 开始剩余石子当前玩家能拿到的最大分差- 前缀和 preSum[i] 前 i 个石子总和状态转移1. 从后往前遍历2. 当前玩家两种选择- 直接拿前 i1 个≥2收益 preSum[i1] - dp[i1]- 不拿继承后面最优 dp[i1]3. 取最大值 dp[i] max(preSum[i1] - dp[i1], dp[i1])答案 dp[1] 至少拿2个从下标1开始TypeScript 代码实现typescriptfunction 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])); // 4console.log(stoneGameVIII([7,-6,5,10,5,-2,-6])); // 13console.log(stoneGameVIII([-10,-12])); // -22空间优化一维压缩 O(1)不需要完整 dp 数组只用一个变量记录后一项即可typescriptfunction 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状态转移的博弈论逻辑或者手写一遍递归记忆化版本吗