千问 LeetCode 1872.石子游戏 VIII public int stoneGameVIII(int[] stones)

这是一道经典的博弈论动态规划问题。我们需要结合前缀和与逆向思维来解决。 核心思路1. 游戏规则分析* 操作每次移除最左边的 x 个石子x 1获得这些石子的分数和并在最左边放一个价值为该和的新石子。* 本质无论怎么操作每次移除的石子实际上都是原数组的一个前缀。* 比如原数组是 [A, B, C, D]。* 如果 Alice 拿走前 2 个 [A, B]得分 AB数组变为 [AB, C, D]。* 接下来 Bob 如果拿走前 2 个 [AB, C]得分 ABC。注意这相当于 Bob 拿走了原数组的前 3 个元素的前缀和。* 结论游戏的过程就是双方轮流选择原数组的一个前缀和作为得分且选择的位置必须比上一次选择的位置更靠右。2. 动态规划定义设 prefix[i] 为前 i 个石子的价值之和前缀和。设 dp[i] 表示当游戏进行到必须从第 i 个石子下标 i之后开始选择前缀时当前先手玩家能获得的最大分数差当前玩家分数 - 对手分数。3. 状态转移对于 dp[i]当前玩家有两种选择1. 不选当前位置留给后面这相当于直接变成 dp[i1] 的状态但这在逻辑上通常合并到下一种情况考虑。2. 选择拿走前 k 个石子结束位置为 k其中 k i* 当前玩家得分prefix[k]。* 剩下的局面对手变成了先手从位置 k1 开始。* 对手的优势dp[k1]。* 当前玩家的净胜分prefix[k] - dp[k1]。我们要最大化这个净胜分。即dp[i] max(prefix[k] - dp[k1])其中 k 从 i 到 n-1。4. 优化直接计算上面的转移方程是 O(N^2)。我们可以发现dp[i] 其实依赖于后面所有 prefix[k] - dp[k1] 的最大值。我们可以维护一个后缀最大值 max_val。从后往前遍历dp[i] max_valmax_val max(max_val, prefix[i] - dp[i])特别注意题目规定第一次操作必须拿走至少 2 个石子x 1所以 Alice 的第一次选择不能只拿第 0 个石子她必须从下标 1 或更后面结束。因此最终答案是 dp[1]表示从下标 1 开始做决策或者说第一次操作至少覆盖到下标 1。 Java 代码实现class Solution {public int stoneGameVIII(int[] stones) {int n stones.length;// 1. 计算前缀和// prefix[i] 表示前 i 个石子的和 (stones[0]...stones[i-1])int[] prefix new int[n 1];for (int i 0; i i时的最大分差// 实际上我们只需要维护一个后缀最大值即可不需要完整的 dp 数组// 初始化如果只剩最后一个石子下标 n-1无法操作分差为 0// 但我们的状态定义是基于前缀和的结束位置。// 令 maxVal 表示 max(prefix[k] - dp[k]) 对于所有 k i// 从后往前推// 当 i n-1 时只能拿走所有剩余即整个前缀得分为 prefix[n]// 此时对手没得玩分差就是 prefix[n]int maxVal prefix[n];// 我们从 n-2 开始倒推因为 in-1 的情况已经作为初始值// 最终我们需要求的是 dp[1]因为第一次必须拿 x1即至少拿到下标 1for (int i n - 1; i 1; i--) {// 当前的 dp[i] 就是之前的 maxVal// 这里的逻辑是dp[i] max(prefix[k] - dp[k]) for k i// 但我们需要更新 maxVal 供 i-1 使用// 新的选择是拿走前 i 个得分 prefix[i]对手面对 i对手优势 dp[i]// 所以新产生的差值是 prefix[i] - maxVal (注意这里的 maxVal 其实是上一轮的 dp[i1] 这一层的最优解)// 修正逻辑// 我们用 maxVal 记录 max(prefix[k] - dp[k])// 当前 dp[i] maxVal// 然后更新 maxVal max(maxVal, prefix[i] - dp[i])int currentDp maxVal;maxVal Math.max(maxVal, prefix[i] - currentDp);}// 最后 maxVal 存储的是 i1 时的最优解因为循环最后更新了一次// 实际上上面的循环逻辑稍微有点绕我们用更清晰的写法// 重新梳理清晰版逻辑// dp[i] max(prefix[k] - dp[k]) for k i// 令 f[i] prefix[i] - dp[i]// 则 dp[i] max(f[k]) for k i// 我们维护 suffixMax max(f[k])int[] dp new int[n 1];// 边界dp[n] 0 (没石子了)// f[n] prefix[n] - 0 prefix[n]int suffixMax prefix[n];// 从 n-1 倒推到 1for (int i n - 1; i 1; i--) {dp[i] suffixMax;// 更新 suffixMax加入当前的 f[i]suffixMax Math.max(suffixMax, prefix[i] - dp[i]);}return dp[1];}} 简化后的最终代码class Solution {public int stoneGameVIII(int[] stones) {int n stones.length;// 1. 计算前缀和for (int i 1; i 1Alice 第一次至少拿 2 个即下标 0 和 1所以第一次操作至少结束于下标 1for (int i n - 2; i 1; i--) {// 当前这一步的最优解是max(之前的最优解, 拿走前 i 个 - 对手的最优解)// 这里的逻辑是dp[i] max(suffixMax)// 然后更新 suffixMax max(suffixMax, prefix[i] - dp[i])// 这里的 maxVal 实际上代表的是 dp[i1] 及其后续的最优值即后缀最大值// 当前玩家如果选择拿走到 i得分 stones[i]对手面临局面 i1 (实际上是 i1 开始的后缀)// 但我们的状态定义是maxVal 已经是后面所有选择中的最大值了// 修正// 当前 dp[i] maxVal// 新的候选值stones[i] - dp[i]// 更新 maxValint currentDp maxVal;maxVal Math.max(maxVal, stones[i] - currentDp);}return maxVal;}}⏱️ 复杂度分析* 时间复杂度O(N)只需要一次遍历计算前缀和一次倒序遍历计算 DP。* 空间复杂度O(1)如果允许修改原数组则不需要额外空间否则为 O(N) 用于前缀和。 关键点总结1. 前缀和每次操作本质上是取原数组的前缀和。2. 博弈 DPdp[i] max(score[k] - dp[k1])即“我拿的分数”减去“对手在剩余局面下的最优优势”。3. 后缀最大值优化避免 O(N^2) 的循环通过维护后缀最大值将复杂度降为 O(N)。4. 边界条件Alice 第一次必须拿 x1所以答案是从下标 1 开始计算的 dp[1]。