石子游戏 VIII

题目描述
Alice 和 Bob 玩一个石子游戏，给定一个整数数组 stones，其中 stones[i] 表示第 i 堆石子的数量。游戏规则如下：

1. Alice 先手，两人轮流从数组的开头或结尾取走一堆石子。
2. 每次取走一堆石子后，剩下的石子堆会自动合并（保持顺序），并生成一个新的数组，新数组的每个元素是原始相邻石子堆的和（具体来说，取走第 i 堆后，数组长度减 1，且新位置 i-1 的元素变为原 stones[i-1] + stones[i]（如果 i 是开头，则从 i+1 开始合并））。
3. 游戏进行到只剩一堆石子时结束。
4. 每次取走石子时，玩家得到这堆石子的数量作为分数。
   假设两人都发挥最佳水平，Alice 的目标是最大化自己与 Bob 的分数差（即自己的总得分减去 Bob 的总得分）。问最终 Alice 能得到的最大分数差是多少？

解题过程

这道题的关键在于理解“取走石子后合并相邻堆”的规则。我们需要用一个区间动态规划来模拟这个过程，但需注意：每次操作后，数组的长度和元素值都会变化，直接定义 dp[i][j] 为区间 [i, j] 上的最优差值可能不够，因为区间和会因之前的操作而改变。

我们可以换个角度思考：

• 游戏开始时，数组为 stones。
• 每次操作，玩家从当前数组的两端取走一堆石子，然后将取走位置相邻的两堆（如果存在）合并为一堆。
• 这意味着，随着游戏的进行，数组中的“堆”实际是由原始数组中连续的若干堆合并而成的。

更形式化地说，设 prefix[i] 为原始数组的前缀和，即 prefix[0]=0, prefix[i] = stones[0]+...+stones[i-1]。
如果当前剩下的区间是原始数组的连续子数组 [l, r]（下标从 0 开始），那么这个区间内合并后的堆对应的石子数，实际上是原数组的一段和。
但要注意，当我们从该区间的左端或右端取走一堆时，取走的是这个“合并堆”，它对应原始数组中的一段连续石子。

实际上，可以证明，在任何时候，剩下的数组可以看作由原始数组的若干连续段组成。但本题有一个更巧妙的转化：
定义 dp[l][r] 表示当前剩下的石子是原始数组中从 l 到 r 的连续子数组时，先手玩家在这一段上能获得的最大分数差（先手总得分减去后手总得分）。

但这里有个问题：当从两端取石子时，剩下的数组不一定是原始数组的一个连续子数组，因为取走后合并会改变边界。
例如原始数组 [a,b,c,d]，若先手取走 a，则剩下 [a+b, c, d]，这对应于原始数组的 [0,3] 但内部合并过一次，不再保持原始连续子数组结构。
因此直接用原始下标区间表示状态不够方便。

一个常见的技巧是：将“合并相邻堆”的规则，转化为“每次取走石子时，实际上取走了原始数组中某个连续段的和”。
可以这样建模：

• 设数组长度为 n。
• 在任何时候，剩下的石子堆对应于原始数组的一个划分，即若干个连续段。
• 当从一端取走一堆时，实际上是取走了当前最左或最右的连续段，并将相邻的两段合并。

经过推导，可以发现，这个游戏等价于：
初始有 n 堆石子，每次操作，玩家可以选择当前数组的最左端或最右端的一堆取走，得分等于这堆的石子数，然后将这堆石子与相邻的一堆合并。
合并后，相邻堆的石子数变为两堆之和。

这种合并规则使得问题可以转化为区间 DP，但状态需要记录“当前区间是原始数组的哪个连续段，且左右端点是否已经被合并过”。这会使状态变复杂。

但本题有一个更简单的思路（来自类似题目的经典解法）：
用 dp[i] 表示当剩下的石子对应于原始数组的前缀和区间 [0, i] 合并后的某个状态时的最优差值，但这种转化不够直接。

实际上，我们可以通过反向思考来解决：
设 dp[i][j] 表示当前剩下的石子是原始数组中的连续段 [i, j]，且这一段还没有被合并过（即这一段目前就是一整堆），先手玩家能获得的最大分数差。
那么初始时，整个数组是 [0, n-1] 这一段，但一开始它是多堆，不是一整堆，所以不能直接用这个状态。

但我们可以考虑最后一步：当只剩一堆时，游戏结束，没有操作，分数差为 0。
从最后一步向前推，我们可以设计另一个 DP：
dp[l][r] 表示当前数组只剩下原始数组中从 l 到 r 的这些石子（可能内部已经合并过，但我们不关心内部细节），先手在当前局面能获得的最大分数差。
为了计算 dp[l][r]，我们考虑先手的选择：

1. 取走左边第一堆（即原始数组下标 l 开始的一段连续石子，其长度可以是 1 到 r-l+1 的任意值，但实际上，因为合并规则，左边第一堆一定对应原始数组的 [l, k] 段，其中 k 是某个位置，且这一段是当前数组的第一堆）。
2. 取走右边第一堆（即原始数组的 [m, r] 段，这一段是当前数组的最后一堆）。

如果我们知道当前数组的第一堆对应原始数组的哪一段，就可以知道得分，然后剩下的数组变成原始数组的 [k+1, r] 或 [l, m-1]，并且这两段内部可能还包含多堆。
但这样状态就太复杂了，我们需要记录第一堆的结束位置。

不过本题实际上可以用记忆化搜索配合递归来实现，状态为 (l, r, leftLen, rightLen)，表示当前数组的最左堆对应原始数组的 [l, l+leftLen-1]，最右堆对应 [r-rightLen+1, r]，中间的 [l+leftLen, r-rightLen] 段是未合并的原始石子堆（各自独立）。
但这样状态数是 O(n^4)，在 n 较小时可行，但 n 大时不行。

由于本题是经典的石子游戏 VIII，它有更简洁的解法：
可以证明，最优策略下，玩家总是取当前数组的一端，并且合并后，新数组的每个元素等于原始数组中某个连续子数组的和，且这些连续子数组正好构成原始数组的一个划分。
进一步，这个问题等价于：
每次操作，玩家从当前数组两端选一堆取走，得分等于这堆的石子数，然后将这堆与相邻堆合并。
这等价于每次操作是将原始数组中某个前缀或后缀的和加入得分，然后删掉那一段。

最终，可以推导出：设 prefix[i] 是前缀和，则先手的得分为某些 prefix[k] 的和，后手得分为另一些 prefix[m] 的和。
经过推导，最优策略是：每次取走一端，使得剩下的数组的“总价值”对先手最有利。
最终结果可以用以下递推公式计算：
设 dp[i] 表示当剩下的石子是原始数组中从 i 到 n-1 的连续段时，先手能获得的最大分数差。
递推：
dp[i] = max( stones[i] - dp[i+1], stones[i] + stones[i+1] - dp[i+2], ..., sum(i..n-1) - dp[n] )，
其中 dp[n] = 0。
但这样是 O(n^2) 的，可以用前缀和优化。

然而，这个递推是基于“从左边取”的假设，实际上游戏可以从两端取，所以我们需要一个二维 DP 来考虑左右两端。

标准解法（二维 DP）
定义 dp[l][r] 表示当剩下的石子对应于原始数组的子数组 stones[l..r]，且这个子数组目前是一整个合并后的堆（即这一段在游戏中被视为一堆）时，先手能获得的最大分数差。
那么初始时，整个数组不是一整个堆，但我们可以认为游戏开始时，我们有 n 个长度为 1 的堆，即 dp[i][i] = stones[i]（因为只剩一堆时，先手取走它，得分为 stones[i]，后手为 0，差值就是 stones[i]）。

递推：
对于长度大于 1 的区间 [l, r]，当前先手有两种选择：

1. 取走这一整堆（得分为 sum(l, r)），然后剩下的数组是去掉这个区间后的部分，但剩下的部分可能被合并，我们需要知道剩下部分的状态。
   不过，当取走这一整堆后，游戏可能结束，如果这是最后一堆，则差值为 sum(l, r)。否则，剩下的部分会形成一个新的区间，但我们不知道它是哪一段。
   所以这个定义不够好。

实际上，正确的状态定义是：
dp[l][r] 表示当前剩下的石子堆正好对应原始数组的 [l, r] 区间，且这个区间目前是一个整体（即一堆），先手在当前局面能获得的最大分数差。
那么，当前先手可以取走这一整堆，得分为 S(l, r)，然后剩下的石子是原始数组中除去 [l, r] 的部分，但那些部分可能已经被合并成若干堆。
这样问题就分解为两个独立的子游戏：左边 [0, l-1] 和右边 [r+1, n-1]。
但这两个子游戏是独立的，且先手在取走当前堆后变成后手。
所以，如果先手取走当前堆，他得到的分数差是：
S(l, r) - max( dp[0][l-1], dp[r+1][n-1] 中的最优值？)
这里并不简单，因为左右两段是分开的，对手可以选择在任意一段中操作，所以我们需要一个更整体的状态。

鉴于这个问题的复杂性，竞赛中常用记忆化搜索实现，状态为 (l, r) 表示当前数组对应原始数组的连续段 [l, r]，且这个段内还没有进行过任何合并（即初始状态）。
在状态 (l, r) 中，先手有两种选择：

• 取左端一堆，即取走 stones[l]，然后 stones[l] 和 stones[l+1] 合并（如果 l+1 ≤ r），新区间变成 [l+1, r] 但第一堆是 stones[l]+stones[l+1]，其余不变。这等价于状态 (l+1, r) 但第一堆的值增加了 stones[l]，所以得分是 stones[l]，然后转入状态 (l+1, r) 且先手变成后手。
• 取右端一堆，即取走 stones[r]，然后 stones[r-1] 和 stones[r] 合并，新区间是 [l, r-1] 但最后一堆变成 stones[r-1]+stones[r]，得分是 stones[r]，然后转入状态 (l, r-1) 且先手变成后手。

因此，我们可以写出递推：
dp[l][r] = max( stones[l] - dp[l+1][r], stones[r] - dp[l][r-1] )。
这里 dp[l][r] 表示在区间 [l, r] 上先手能获得的最大分数差。
这个递推假设了“合并”操作不改变区间内其他堆的值，但实际合并会改变相邻堆的值，所以这个简单的递推是错误的。

为了处理合并，我们可以在状态中记录区间边界堆的“额外重量”，但这样状态变成 (l, r, left_extra, right_extra)，表示左边界堆在原 stones[l] 基础上加了 left_extra，右边界堆在原 stones[r] 基础上加了 right_extra。
这样，当取左堆时，得分为 stones[l] + left_extra，然后左边界消失，新的左边界是原 stones[l+1] 加上 left_extra（因为合并），所以新状态是 (l+1, r, left_extra + stones[l+1], right_extra)。
取右堆类似。
初始状态为 (0, n-1, 0, 0)。

这样我们可以用记忆化搜索计算，状态数 O(n^2)，每个状态转移 O(1)。

最终算法步骤

1. 设 n = stones.length。
2. 定义记忆化数组 memo[l][r][le][re]，但 le 和 re 可能很大（累加石子数），所以用哈希表存储状态。
3. 定义递归函数 solve(l, r, le, re)：
   • 如果 l > r，返回 0（无石子，得分差 0）。
   • 计算取左端的得分：scoreL = stones[l] + le。
     新状态：nl = l+1, nle = le + stones[nl] (如果 nl <= r), 否则 0。
     差值为 scoreL - solve(nl, r, nle, re)。
   • 计算取右端的得分：scoreR = stones[r] + re。
     新状态：nr = r-1, nre = re + stones[nr] (如果 l <= nr), 否则 0。
     差值为 scoreR - solve(l, nr, le, nre)。
   • 返回两者最大值。
4. 答案 = solve(0, n-1, 0, 0)。

由于 le 和 re 可能很大，我们可以用另一种表示：
设 total[l][r] 表示原数组 stones[l..r] 的和，
状态 (l, r) 表示当前区间，且左边界堆的值 = total[l][k]，右边界堆的值 = total[m][r]，但这样又需要记录 k 和 m，状态 O(n^4) 会太大。

实际上，有一个技巧：合并操作可以视为“取走一堆后，它的值加到相邻堆上”，因此我们可以用 (l, r, left_extra) 表示状态，其中 left_extra 是当前左边界堆的额外值（即原 stones[l] 被加上的额外值），右边界类似。但这样需要两个额外值。

更简洁的方法（标准解法）
经过推导，可以证明本题等价于：
每次操作，玩家从当前数组两端取一堆，得分是这堆的值，然后这堆的值加到相邻堆上。
这等价于：设前缀和 prefix[i] = stones[0]+...+stones[i-1]，每次取左端时，得分为 prefix[l+1] - prefix[l] + left_extra，等等。
最终，可以转化为一个一维 DP：
定义 f[i] 表示当剩下的石子是 stones[i..n-1] 时，先手能获得的最大分数差。
递推：
f[i] = max( sum(i..j) - f[j+1] ) 对 j 从 i 到 n-1，
因为取走 stones[i..j] 这一段（作为左端一堆），得分为 sum(i..j)，然后剩下 stones[j+1..n-1]，此时先手变成后手，所以减去 f[j+1]。
初始 f[n] = 0。
同样考虑从右端取的情况对称，但上述递推已经包含（因为取右端等价于取一段后缀）。
计算时，我们可以用前缀和快速求 sum(i..j)，总复杂度 O(n^2)。

最终递推

n = len(stones)
prefix = [0]*(n+1)
for i in range(n):
    prefix[i+1] = prefix[i] + stones[i]
def sum_range(l, r):
    return prefix[r+1] - prefix[l]

dp = [0]*(n+1)
for i in range(n-1, -1, -1):
    dp[i] = -10**9
    for j in range(i, n):
        dp[i] = max(dp[i], sum_range(i, j) - dp[j+1])
return dp[0]

但这是 O(n^2) 时间，可以优化到 O(n) 因为 dp[i] = max( sum_range(i, j) - dp[j+1] ) = prefix[j+1] - prefix[i] - dp[j+1]，所以 dp[i] = max_{j>=i} ( prefix[j+1] - dp[j+1] ) - prefix[i]。
因此我们可以从后往前维护 max_prefix_minus_dp = max( prefix[j+1] - dp[j+1] )，则 dp[i] = max_prefix_minus_dp - prefix[i]。

最终 O(n) 解法：

n = len(stones)
prefix = [0]*(n+1)
for i in range(n):
    prefix[i+1] = prefix[i] + stones[i]
dp = [0]*(n+1)
max_val = prefix[n] - dp[n]  # = prefix[n]
for i in range(n-1, -1, -1):
    dp[i] = max_val - prefix[i]
    max_val = max(max_val, prefix[i] - dp[i])
return dp[0]

这就是最终答案。

总结
本题的关键是将游戏规则转化为“每次取走一段连续石子，得分是该段和，然后剩下部分继续游戏”的模型，然后推导出一维 DP 递推，并用前缀和优化到 O(n)。最后答案是 dp[0]，即从整个数组开始先手能获得的最大分数差。