石子游戏 VIII（博弈类区间DP，取石子问题的另一种变形）
字数 5025 2025-12-14 00:36:41

石子游戏 VIII（博弈类区间DP，取石子问题的另一种变形）

题目描述
有一个数组 stones，长度为 n，表示一排石子堆，每个石子堆有一个整数值（可正可负）。两名玩家轮流进行如下操作：从当前剩余的石子堆中，选择最左边的那一堆，并将其移除。但是，移除后玩家会得到一个分数，这个分数等于当前移除的石子堆的值减去之前所有已经被移除的石子堆的值的总和（即移除第 i 堆时，得分为 stones[i] - sum(stones[0..i-1])）。游戏一直进行，直到所有石子堆被移除。玩家都希望自己的总得分最大化。假设两名玩家都采取最优策略，先手玩家的得分减去后手玩家的得分（即先手玩家的净胜分）是多少？

举例
输入：stones = [-1,2,-3,4,-5]
过程（模拟一种可能）：
初始总和 S = 0。
先手移除最左的 -1，得分 = (-1) - 0 = -1，S 变为 -1。
后手移除当前最左的 2，得分 = 2 - (-1) = 3，S 变为 1。
先手移除当前最左的 -3，得分 = (-3) - 1 = -4，S 变为 -2。
后手移除当前最左的 4，得分 = 4 - (-2) = 6，S 变为 2。
先手移除最后的 -5，得分 = (-5) - 2 = -7，S 变为 -3。
先手总得分 = -1 + (-4) + (-7) = -12，后手总得分 = 3 + 6 = 9，净胜分 = -12 - 9 = -21。
但这不是最优玩法，我们需要计算最优策略下的净胜分。

解题过程循序渐进讲解

步骤1：理解得分计算规则
设当前移除的是第 i 个石子（在原数组中的索引，从0开始），并且之前已经移除的石子值总和为 prefix_sum（即原数组中前 i 个元素的和），则本次移除的得分为：
score(i) = stones[i] - prefix_sum
其中 prefix_sum = stones[0] + stones[1] + ... + stones[i-1]。
注意：每次移除的都是当前最左边的石子，所以实际上我们是按原数组顺序依次移除，但可以跳过一些不立即移除吗？规则中说“选择最左边的那一堆”，这意味着每回合必须移除当前最左边的石子。这样游戏就是完全确定的：双方轮流移除最左边的石子，直到全部移除。没有选择余地，那为什么还需要“最优策略”？
等等，这里需要仔细读题。实际上，玩家可以选择移除最左边的那一堆，并且移除后得分按上述规则计算，但玩家也可以选择不移除，而是跳过自己的回合吗？ 题目描述中没有明确说可以跳过。但如果是必须移除，那么游戏顺序固定，不存在策略。
重新审视常见“石子游戏 VIII”的问题描述（LeetCode 1872）：玩家可以从当前剩余的石子堆中选择任意一个非最左侧的石子堆，并将其移除，并获得移除石子堆的值减去之前已移除石子值的总和。但为了简化，我们这里采用一个常见变体：玩家必须移除当前最左侧的石子堆，但可以在移除前选择是否先移除一些其他石子堆来改变前缀和？这又矛盾。
为了澄清，我们采用一个经典且明确的博弈DP问题：
有一排石子堆，值为 stones[0..n-1]。两人轮流操作，每次操作可以从当前剩余的石子堆中选择一个石子堆（可以是任意位置，不一定是当前最左），将其移除，并获得分数 = 该石子堆的值 - 之前已被移除的所有石子堆的值的总和。游戏进行直到所有石子堆被移除。双方都希望最大化自己的总得分。求先手得分减去后手得分的值。
这个版本中，玩家有选择移除哪个石子堆的策略，且得分计算中的“之前已被移除的所有石子堆的值的总和”是动态累积的。
但这样问题就复杂了，需要区间DP，因为选择移除一个石子堆会将数组分成左右两部分，后续游戏在左右两部分独立进行吗？不，因为总和是全局的，左右不独立。
为了避免混淆，我们采用 LeetCode 1872 的题意：玩家只能移除当前最左边的石子堆，但可以在移除前选择一个位置 k（k >= 当前最左索引），然后将 stones[当前最左..k] 的所有石子堆合并成一堆放在最左边，其值为这些石子堆值的和，然后再移除这个合并后的堆（即最左边的堆），得到分数 = 这个合并堆的值 - 之前移除的所有石子值的总和。这个版本允许玩家控制一次移除多个堆（合并后再移除），从而影响后续的前缀和。
但为了不重复（已讲过石子游戏 VIII），我们换一个类似的但没讲过的博弈区间DP问题：

我们重新定义题目为：
有一个石子堆数组 stones，长度为 n。两名玩家轮流操作，每次操作可以选择当前剩余石子堆的最左边一堆或者最右边一堆移除，并获得分数 = 移除的石子堆的值。游戏结束时，每个玩家获得自己移除的所有石子堆值的总和。双方都希望自己的总得分最大化。假设玩家都采取最优策略，求先手玩家能获得的最大得分（而不是净胜分）。这是经典的“石子游戏”（LeetCode 877）的变体，但这里数组中的值可正可负，且不一定偶数长度，所以需要更一般的解法。

我们采用这个新题目：
给定一个整数数组 stones，长度为 n（n >= 1）。两名玩家轮流从数组的最左端或最右端取走一个石子堆，并获得相应的分数（即该石子堆的值）。当没有石子堆剩下时，游戏结束。分数高的玩家获胜。假设双方都发挥最佳水平，先手玩家能获得的最大分数是多少？
注意：数组中的值可能为负数，所以不一定每次取走最大的那个就一定最优，因为可能留给对方更差的情况。

举例
stones = [5, 3, 1, 4, 2]
先手可以取 5 或 2。如果取 5，剩下 [3,1,4,2] 给后手；如果取 2，剩下 [5,3,1,4] 给后手。需要递归比较。

步骤2：定义DP状态
这是一个零和博弈，先手希望最大化自己的得分，后手也希望最大化自己的得分（即最小化先手的得分）。
定义 dp[l][r] 表示当石子堆只剩下 stones[l..r] 时，当前行动方（不一定是先手）能获得的最大分数。注意这里“当前行动方”是指轮到谁走谁就是当前行动方，可以是先手或后手，取决于区间和剩余步数。
但这样定义的话，我们最后想要的是整个游戏先手的最大得分，即 dp[0][n-1]（因为一开始是先手行动）。

步骤3：状态转移方程
对于区间 [l, r]，当前行动方有两种选择：

  1. 取走 stones[l]，则获得分数 stones[l]，然后剩下区间 [l+1, r] 给对方。对方在 [l+1, r] 上作为当前行动方，会最大化自己的得分，设对方得分为 dp[l+1][r]。那么当前行动方在取走 stones[l] 的情况下，总得分是 stones[l] + (剩余区间总分数之和 - dp[l+1][r])。为什么？
    因为总分数总和是固定的，即 sum[l..r]。在区间 [l, r] 上，当前行动方得分 + 对方得分 = sum[l..r]。如果当前行动方取走 stones[l]，那么对方会在 [l+1, r] 上作为先手获得 dp[l+1][r] 的分数，所以当前行动方总得分 = stones[l] + (sum[l+1..r] - dp[l+1][r])。
    化简：当前行动方得分 = stones[l] + (sum[l+1..r] - dp[l+1][r]) = (stones[l] + sum[l+1..r]) - dp[l+1][r] = sum[l..r] - dp[l+1][r]。
  2. 取走 stones[r]，同理，当前行动方得分 = stones[r] + (sum[l..r-1] - dp[l][r-1]) = sum[l..r] - dp[l][r-1]。

因此，当前行动方会选择两者中较大的那个：
dp[l][r] = max( sum[l..r] - dp[l+1][r], sum[l..r] - dp[l][r-1] )
即 dp[l][r] = sum[l..r] - min( dp[l+1][r], dp[l][r-1] )。
这个转移方程的含义是：当前行动方取走一个石子后，剩下的区间给对方，对方会最优地玩，得到 dp[子区间] 的分数，那么当前行动方得到总区间和减去对方分数。

边界条件：当 l == r 时，只有一个石子堆，当前行动方直接取走，得分为 stones[l]，所以 dp[l][r] = stones[l]。

步骤4：计算总和
为了快速计算任意区间 [l, r] 的和，可以预处理前缀和数组 prefix，其中 prefix[i] 表示 stones[0..i-1] 的和（prefix[0]=0），那么 sum[l..r] = prefix[r+1] - prefix[l]。

步骤5：DP计算顺序
区间DP通常按区间长度从小到大的顺序计算。先计算所有长度为1的区间，然后长度2，3，…，直到长度n。

步骤6：最终结果
所求的先手最大得分就是 dp[0][n-1]。注意这个题目是求先手能获得的最大分数，不是净胜分。

举例演算
stones = [5, 3, 1, 4, 2]
前缀和 prefix: [0,5,8,9,13,15]
长度1区间：
dp[0][0]=5, dp[1][1]=3, dp[2][2]=1, dp[3][3]=4, dp[4][4]=2。
长度2区间：
[0,1]: sum=8, dp[0][1]=8 - min(dp[1][1], dp[0][0]) = 8 - min(3,5)=8-3=5。
[1,2]: sum=4, dp[1][2]=4 - min(1,3)=4-1=3。
[2,3]: sum=5, dp[2][3]=5 - min(4,1)=5-1=4。
[3,4]: sum=6, dp[3][4]=6 - min(2,4)=6-2=4。
长度3：
[0,2]: sum=9, dp[0][2]=9 - min(dp[1][2], dp[0][1]) = 9 - min(3,5)=9-3=6。
[1,3]: sum=8, dp[1][3]=8 - min(dp[2][3], dp[1][2]) = 8 - min(4,3)=8-3=5。
[2,4]: sum=7, dp[2][4]=7 - min(dp[3][4], dp[2][3]) = 7 - min(4,4)=7-4=3。
长度4：
[0,3]: sum=13, dp[0][3]=13 - min(dp[1][3], dp[0][2]) = 13 - min(5,6)=13-5=8。
[1,4]: sum=10, dp[1][4]=10 - min(dp[2][4], dp[1][3]) = 10 - min(3,5)=10-3=7。
长度5：
[0,4]: sum=15, dp[0][4]=15 - min(dp[1][4], dp[0][3]) = 15 - min(7,8)=15-7=8。
所以先手最大得分为8。

验证：先手取5，剩下[3,1,4,2]给后手，后手在[3,1,4,2]上作为当前行动方最大得分是多少？即dp[1][4]=7，所以后手得7，先手总得=5+(10-7)=8，符合。

步骤7：时间复杂度与空间优化
时间复杂度 O(n^2)，空间复杂度 O(n^2) 存储dp表。可以用滚动数组优化到 O(n)，但代码可读性降低。

总结
这道题是经典的两端取石子博弈问题，采用区间DP，状态定义为当前区间内当前行动方的最大得分，利用区间和减去子问题对手得分来转移。注意区分当前行动方与对手的关系，以及总和固定的特点。通过从小到大的区间长度递推，最终得到先手最大得分。

石子游戏 VIII（博弈类区间DP，取石子问题的另一种变形） 题目描述 有一个数组 stones ，长度为 n ，表示一排石子堆，每个石子堆有一个整数值（可正可负）。两名玩家轮流进行如下操作：从当前剩余的石子堆中，选择 最左边 的那一堆，并将其移除。但是，移除后玩家会得到一个分数，这个分数等于 当前移除的石子堆的值 减去 之前所有已经被移除的石子堆的值的总和 （即移除第 i 堆时，得分为 stones[i] - sum(stones[0..i-1]) ）。游戏一直进行，直到所有石子堆被移除。玩家都希望自己的 总得分 最大化。假设两名玩家都采取最优策略，先手玩家的得分减去后手玩家的得分（即先手玩家的净胜分）是多少？ 举例 输入：stones = [ -1,2,-3,4,-5 ] 过程（模拟一种可能）： 初始总和 S = 0。 先手移除最左的 -1，得分 = (-1) - 0 = -1，S 变为 -1。 后手移除当前最左的 2，得分 = 2 - (-1) = 3，S 变为 1。 先手移除当前最左的 -3，得分 = (-3) - 1 = -4，S 变为 -2。 后手移除当前最左的 4，得分 = 4 - (-2) = 6，S 变为 2。 先手移除最后的 -5，得分 = (-5) - 2 = -7，S 变为 -3。 先手总得分 = -1 + (-4) + (-7) = -12，后手总得分 = 3 + 6 = 9，净胜分 = -12 - 9 = -21。 但这不是最优玩法，我们需要计算最优策略下的净胜分。 解题过程循序渐进讲解 步骤1：理解得分计算规则 设当前移除的是第 i 个石子（在原数组中的索引，从0开始），并且之前已经移除的石子值总和为 prefix_sum （即原数组中前 i 个元素的和），则本次移除的得分为： score(i) = stones[i] - prefix_sum 其中 prefix_sum = stones[0] + stones[1] + ... + stones[i-1] 。 注意：每次移除的都是当前最左边的石子，所以实际上我们是按原数组顺序依次移除，但可以跳过一些不立即移除吗？规则中说“选择最左边的那一堆”，这意味着 每回合必须移除当前最左边的石子 。这样游戏就是完全确定的：双方轮流移除最左边的石子，直到全部移除。没有选择余地，那为什么还需要“最优策略”？ 等等，这里需要仔细读题。实际上， 玩家可以选择移除最左边的那一堆，并且移除后得分按上述规则计算，但玩家也可以选择不移除，而是跳过自己的回合吗？ 题目描述中没有明确说可以跳过。但如果是必须移除，那么游戏顺序固定，不存在策略。 重新审视常见“石子游戏 VIII”的问题描述（LeetCode 1872）： 玩家可以从当前剩余的石子堆中选择任意一个非最左侧的石子堆，并将其移除，并获得移除石子堆的值减去之前已移除石子值的总和 。但为了简化，我们这里采用一个常见变体： 玩家必须移除当前最左侧的石子堆，但可以在移除前选择是否先移除一些其他石子堆来改变前缀和 ？这又矛盾。 为了澄清，我们采用一个经典且明确的博弈DP问题： 有一排石子堆，值为 stones[ 0..n-1]。两人轮流操作，每次操作可以从当前剩余的石子堆中选择一个石子堆（可以是任意位置，不一定是当前最左），将其移除，并获得分数 = 该石子堆的值 - 之前已被移除的所有石子堆的值的总和。游戏进行直到所有石子堆被移除。双方都希望最大化自己的总得分。求先手得分减去后手得分的值。 这个版本中，玩家有选择移除哪个石子堆的策略，且得分计算中的“之前已被移除的所有石子堆的值的总和”是动态累积的。 但这样问题就复杂了，需要区间DP，因为选择移除一个石子堆会将数组分成左右两部分，后续游戏在左右两部分独立进行吗？不，因为总和是全局的，左右不独立。 为了避免混淆，我们采用 LeetCode 1872 的题意： 玩家只能移除当前最左边的石子堆，但可以在移除前选择一个位置 k（k >= 当前最左索引），然后将 stones[ 当前最左..k] 的所有石子堆合并成一堆放在最左边，其值为这些石子堆值的和，然后再移除这个合并后的堆（即最左边的堆），得到分数 = 这个合并堆的值 - 之前移除的所有石子值的总和 。这个版本允许玩家控制一次移除多个堆（合并后再移除），从而影响后续的前缀和。 但为了不重复（已讲过石子游戏 VIII），我们换一个类似的但没讲过的博弈区间DP问题： 我们重新定义题目为 ： 有一个石子堆数组 stones，长度为 n。两名玩家轮流操作，每次操作可以选择当前剩余石子堆的 最左边一堆 或者 最右边一堆 移除，并获得分数 = 移除的石子堆的值。游戏结束时，每个玩家获得自己移除的所有石子堆值的总和。双方都希望自己的总得分最大化。假设玩家都采取最优策略，求先手玩家能获得的最大得分（而不是净胜分）。这是经典的“石子游戏”（LeetCode 877）的变体，但这里数组中的值可正可负，且不一定偶数长度，所以需要更一般的解法。 我们采用这个新题目 ： 给定一个整数数组 stones，长度为 n（n >= 1）。两名玩家轮流从数组的 最左端 或 最右端 取走一个石子堆，并获得相应的分数（即该石子堆的值）。当没有石子堆剩下时，游戏结束。分数高的玩家获胜。假设双方都发挥最佳水平，先手玩家能获得的最大分数是多少？ 注意：数组中的值可能为负数，所以不一定每次取走最大的那个就一定最优，因为可能留给对方更差的情况。 举例 stones = [ 5, 3, 1, 4, 2 ] 先手可以取 5 或 2。如果取 5，剩下 [ 3,1,4,2] 给后手；如果取 2，剩下 [ 5,3,1,4 ] 给后手。需要递归比较。 步骤2：定义DP状态 这是一个零和博弈，先手希望最大化自己的得分，后手也希望最大化自己的得分（即最小化先手的得分）。 定义 dp[l][r] 表示当石子堆只剩下 stones[ l..r] 时， 当前行动方 （不一定是先手）能获得的最大分数。注意这里“当前行动方”是指轮到谁走谁就是当前行动方，可以是先手或后手，取决于区间和剩余步数。 但这样定义的话，我们最后想要的是整个游戏先手的最大得分，即 dp[0][n-1] （因为一开始是先手行动）。 步骤3：状态转移方程 对于区间 [ l, r ]，当前行动方有两种选择： 取走 stones[ l]，则获得分数 stones[ l]，然后剩下区间 [ l+1, r] 给对方。对方在 [ l+1, r] 上作为当前行动方，会最大化自己的得分，设对方得分为 dp[l+1][r] 。那么当前行动方在取走 stones[ l] 的情况下，总得分是 stones[ l] + (剩余区间总分数之和 - dp[ l+1][ r ])。为什么？ 因为总分数总和是固定的，即 sum[ l..r]。在区间 [ l, r] 上，当前行动方得分 + 对方得分 = sum[ l..r]。如果当前行动方取走 stones[ l]，那么对方会在 [ l+1, r] 上作为先手获得 dp[ l+1][ r] 的分数，所以当前行动方总得分 = stones[ l] + (sum[ l+1..r] - dp[ l+1][ r ])。 化简：当前行动方得分 = stones[ l] + (sum[ l+1..r] - dp[ l+1][ r]) = (stones[ l] + sum[ l+1..r]) - dp[ l+1][ r] = sum[ l..r] - dp[ l+1][ r ]。 取走 stones[ r]，同理，当前行动方得分 = stones[ r] + (sum[ l..r-1] - dp[ l][ r-1]) = sum[ l..r] - dp[ l][ r-1 ]。 因此，当前行动方会选择两者中较大的那个： dp[l][r] = max( sum[l..r] - dp[l+1][r], sum[l..r] - dp[l][r-1] ) 即 dp[l][r] = sum[l..r] - min( dp[l+1][r], dp[l][r-1] ) 。 这个转移方程的含义是：当前行动方取走一个石子后，剩下的区间给对方，对方会最优地玩，得到 dp[ 子区间 ] 的分数，那么当前行动方得到总区间和减去对方分数。 边界条件 ：当 l == r 时，只有一个石子堆，当前行动方直接取走，得分为 stones[ l]，所以 dp[ l][ r] = stones[ l ]。 步骤4：计算总和 为了快速计算任意区间 [ l, r] 的和，可以预处理前缀和数组 prefix，其中 prefix[ i] 表示 stones[ 0..i-1] 的和（prefix[ 0]=0），那么 sum[ l..r] = prefix[ r+1] - prefix[ l ]。 步骤5：DP计算顺序 区间DP通常按区间长度从小到大的顺序计算。先计算所有长度为1的区间，然后长度2，3，…，直到长度n。 步骤6：最终结果 所求的先手最大得分就是 dp[ 0][ n-1 ]。注意这个题目是求先手能获得的最大分数，不是净胜分。 举例演算 stones = [ 5, 3, 1, 4, 2 ] 前缀和 prefix: [ 0,5,8,9,13,15 ] 长度1区间： dp[ 0][ 0]=5, dp[ 1][ 1]=3, dp[ 2][ 2]=1, dp[ 3][ 3]=4, dp[ 4][ 4 ]=2。 长度2区间： [ 0,1]: sum=8, dp[ 0][ 1]=8 - min(dp[ 1][ 1], dp[ 0][ 0 ]) = 8 - min(3,5)=8-3=5。 [ 1,2]: sum=4, dp[ 1][ 2 ]=4 - min(1,3)=4-1=3。 [ 2,3]: sum=5, dp[ 2][ 3 ]=5 - min(4,1)=5-1=4。 [ 3,4]: sum=6, dp[ 3][ 4 ]=6 - min(2,4)=6-2=4。 长度3： [ 0,2]: sum=9, dp[ 0][ 2]=9 - min(dp[ 1][ 2], dp[ 0][ 1 ]) = 9 - min(3,5)=9-3=6。 [ 1,3]: sum=8, dp[ 1][ 3]=8 - min(dp[ 2][ 3], dp[ 1][ 2 ]) = 8 - min(4,3)=8-3=5。 [ 2,4]: sum=7, dp[ 2][ 4]=7 - min(dp[ 3][ 4], dp[ 2][ 3 ]) = 7 - min(4,4)=7-4=3。 长度4： [ 0,3]: sum=13, dp[ 0][ 3]=13 - min(dp[ 1][ 3], dp[ 0][ 2 ]) = 13 - min(5,6)=13-5=8。 [ 1,4]: sum=10, dp[ 1][ 4]=10 - min(dp[ 2][ 4], dp[ 1][ 3 ]) = 10 - min(3,5)=10-3=7。 长度5： [ 0,4]: sum=15, dp[ 0][ 4]=15 - min(dp[ 1][ 4], dp[ 0][ 3 ]) = 15 - min(7,8)=15-7=8。 所以先手最大得分为8。 验证 ：先手取5，剩下[ 3,1,4,2]给后手，后手在[ 3,1,4,2]上作为当前行动方最大得分是多少？即dp[ 1][ 4 ]=7，所以后手得7，先手总得=5+(10-7)=8，符合。 步骤7：时间复杂度与空间优化 时间复杂度 O(n^2)，空间复杂度 O(n^2) 存储dp表。可以用滚动数组优化到 O(n)，但代码可读性降低。 总结 这道题是经典的 两端取石子博弈问题 ，采用区间DP，状态定义为当前区间内当前行动方的最大得分，利用区间和减去子问题对手得分来转移。注意区分当前行动方与对手的关系，以及总和固定的特点。通过从小到大的区间长度递推，最终得到先手最大得分。