石子游戏 VII（博弈类区间DP的典型题目）

字数 2976 2025-12-24 11:23:30

石子游戏 VII（博弈类区间DP的典型题目）

一、题目描述

Alice 和 Bob 轮流玩一个石子游戏，规则如下：

有一个非负整数数组 stones，表示一排石子堆，stones[i] 是第 i 堆石子的价值。
游戏进行时，Alice 先手，两人轮流从当前剩余石子堆的两端（最左或最右）移除一堆石子，并获得剩余石子堆的价值总和作为得分。
当石子堆被拿完后游戏结束。
双方都想最大化自己的得分，假设两人都采用最优策略。

目标：返回 Alice 能获得的最大得分差值（即 Alice 得分 − Bob 得分），如果 Alice 无法赢得更多，也可能返回负数。

示例

输入：stones = [5,3,1,4,2]
输出：6
解释：

初始数组总和 = 5+3+1+4+2 = 15
如果 Alice 先拿最左的 5，则她得到剩余和 10（15-5），剩下 [3,1,4,2] 总和 10，Bob 接着在两端选择…
最终 Alice 得分 10 + … 需动态规划计算最优策略。

二、问题分析

这是一个零和博弈问题，Alice 和 Bob 交替操作，每次从两端取一堆石子。
设当前剩余石子为子数组 stones[i..j]，定义 dp[i][j] 表示在当前玩家面对子数组 i..j 时，能获得的最大得分差值（当前玩家得分 − 对手得分）。

注意：当前玩家可能是 Alice 或 Bob，但因为零和博弈，dp 定义是“当前玩家相对于对手的优势差值”，轮到 Alice 时我们希望最大化这个差值，轮到 Bob 时他也想最大化自己的差值，但 Alice 希望 Bob 的差值小，所以状态转移是对称的。

三、状态转移推导

1. 当前剩余石子总和

设 sum[i][j] 为子数组 stones[i..j] 的元素和。为了方便，可以预处理前缀和 prefix，则：

sum[i][j] = prefix[j+1] - prefix[i]

2. 转移方程

当前玩家面对 [i..j] 时有两种选择：

取左端 stones[i]：
当前玩家得到剩余石子堆的和 = sum[i+1][j]（拿走 i 后，剩下的石子堆的总和）
之后轮到对手面对子数组 [i+1..j]，对手的最大差值 = dp[i+1][j]。
所以当前玩家的得分差值 = 本次得分 − 对手在后续的差值：
```
left_gain = sum[i+1][j] - dp[i+1][j]
```
解释：本次得分是 sum[i+1][j]，但对手会在后续比他多 dp[i+1][j] 分（对手视角），所以当前玩家最终差值 = 本次得分 − 对手的优势。
取右端 stones[j]：
当前玩家得到剩余石子堆的和 = sum[i][j-1]
之后对手面对 [i..j-1]，对手的优势 = dp[i][j-1]
```
right_gain = sum[i][j-1] - dp[i][j-1]
```
当前玩家选择更优操作：
```
dp[i][j] = max(left_gain, right_gain)
```

3. 边界条件

当 i == j 时，只剩一堆石子，拿走它后没有剩余石子，所以剩余和为 0，本次得分为 0，没有下一步：

dp[i][i] = 0

因为拿走最后一堆后游戏结束，没有剩余石子可得分。

四、计算顺序与实现细节

区间 DP 通常按长度从小到大计算。
最终答案：Alice 面对 [0, n-1] 时的最大差值 = dp[0][n-1]。

前缀和优化：
sum[i][j] 可以用 prefix[j+1] - prefix[i] 快速得到。

五、逐步计算示例

以 stones = [5,3,1,4,2] 为例，n=5。
前缀和 prefix = [0,5,8,9,13,15]

初始化：dp[i][i] = 0

长度 = 2：

[0,1]: sum[1,1]=3, left_gain = 3 - dp[1][1]=3-0=3
sum[0,0]=5, right_gain = 5 - dp[0][0]=5-0=5
dp[0][1] = max(3,5)=5
[1,2]: sum[2,2]=1, left_gain=1-0=1
sum[1,1]=3, right_gain=3-0=3
dp[1][2] = 3
[2,3]: sum[3,3]=4, left_gain=4, sum[2,2]=1, right_gain=1, dp[2][3]=4
[3,4]: sum[4,4]=2, left_gain=2, sum[3,3]=4, right_gain=4, dp[3][4]=4

长度 = 3：

[0,2]:
sum[1,2]=3+1=4, left_gain = 4 - dp[1][2] = 4-3=1
sum[0,1]=5+3=8, right_gain = 8 - dp[0][1] = 8-5=3
dp[0][2] = max(1,3)=3
[1,3]:
sum[2,3]=1+4=5, left_gain=5-dp[2][3]=5-4=1
sum[1,2]=3+1=4, right_gain=4-dp[1][2]=4-3=1
dp[1][3] = 1
[2,4]:
sum[3,4]=4+2=6, left_gain=6-dp[3][4]=6-4=2
sum[2,3]=1+4=5, right_gain=5-dp[2][3]=5-4=1
dp[2][4] = 2

长度 = 4：

[0,3]:
sum[1,3]=3+1+4=8, left_gain=8-dp[1][3]=8-1=7
sum[0,2]=5+3+1=9, right_gain=9-dp[0][2]=9-3=6
dp[0][3] = 7
[1,4]:
sum[2,4]=1+4+2=7, left_gain=7-dp[2][4]=7-2=5
sum[1,3]=3+1+4=8, right_gain=8-dp[1][3]=8-1=7
dp[1][4] = 7

长度 = 5：

[0,4]:
sum[1,4]=3+1+4+2=10, left_gain=10-dp[1][4]=10-7=3
sum[0,3]=5+3+1+4=13, right_gain=13-dp[0][3]=13-7=6
dp[0][4] = max(3,6)=6

最终结果 = 6，与示例一致。

六、时间复杂度与空间复杂度

时间复杂度：O(n²)，n 为石子堆数，需要计算所有区间。
空间复杂度：O(n²)，dp 表大小。可以优化到 O(n) 但实现稍复杂。

七、总结

石子游戏 VII 是典型的博弈类区间 DP，关键点：

定义 dp[i][j] 为当前玩家在区间 [i..j] 能获得的最大差值（自己得分 − 对手得分）。
转移时，当前玩家取左或右，得到本次得分 = 剩余石子总和，然后减去对手在后续区间的最优差值（因为对手的得分会减少当前玩家的最终优势）。
最终答案即 dp[0][n-1]。

该题在已知总和的情况下，利用前缀和快速计算剩余和，实现简洁高效。

石子游戏 VII（博弈类区间DP的典型题目）一、题目描述 Alice 和 Bob 轮流玩一个石子游戏，规则如下：有一个非负整数数组 stones ，表示一排石子堆， stones[i] 是第 i 堆石子的价值。游戏进行时，Alice 先手，两人轮流从当前剩余石子堆的两端（最左或最右）移除一堆石子，并获得剩余石子堆的价值总和作为得分。当石子堆被拿完后游戏结束。双方都想最大化自己的得分，假设两人都采用最优策略。目标：返回 Alice 能获得的最大得分差值（即 Alice 得分 − Bob 得分），如果 Alice 无法赢得更多，也可能返回负数。示例输入： stones = [5,3,1,4,2] 输出： 6 解释：初始数组总和 = 5+3+1+4+2 = 15 如果 Alice 先拿最左的 5，则她得到剩余和 10（15-5），剩下 [ 3,1,4,2 ] 总和 10，Bob 接着在两端选择… 最终 Alice 得分 10 + … 需动态规划计算最优策略。二、问题分析这是一个零和博弈问题，Alice 和 Bob 交替操作，每次从两端取一堆石子。设当前剩余石子为子数组 stones[i..j] ，定义 dp[i][j] 表示在当前玩家面对子数组 i..j 时，能获得的最大得分差值（当前玩家得分 − 对手得分）。注意：当前玩家可能是 Alice 或 Bob，但因为零和博弈，dp 定义是“当前玩家相对于对手的优势差值”，轮到 Alice 时我们希望最大化这个差值，轮到 Bob 时他也想最大化自己的差值，但 Alice 希望 Bob 的差值小，所以状态转移是对称的。三、状态转移推导 1. 当前剩余石子总和设 sum[i][j] 为子数组 stones[i..j] 的元素和。为了方便，可以预处理前缀和 prefix ，则： 2. 转移方程当前玩家面对 [i..j] 时有两种选择：取左端 stones[i] ：当前玩家得到剩余石子堆的和 = sum[i+1][j] （拿走 i 后，剩下的石子堆的总和）之后轮到对手面对子数组 [i+1..j] ，对手的最大差值 = dp[i+1][j] 。所以当前玩家的得分差值 = 本次得分 − 对手在后续的差值：解释：本次得分是 sum[i+1][j] ，但对手会在后续比他多 dp[i+1][j] 分（对手视角），所以当前玩家最终差值 = 本次得分 − 对手的优势。取右端 stones[j] ：当前玩家得到剩余石子堆的和 = sum[i][j-1] 之后对手面对 [i..j-1] ，对手的优势 = dp[i][j-1] 当前玩家选择更优操作： 3. 边界条件当 i == j 时，只剩一堆石子，拿走它后没有剩余石子，所以剩余和为 0，本次得分为 0，没有下一步：因为拿走最后一堆后游戏结束，没有剩余石子可得分。四、计算顺序与实现细节区间 DP 通常按长度从小到大计算。最终答案：Alice 面对 [0, n-1] 时的最大差值 = dp[0][n-1] 。前缀和优化： sum[i][j] 可以用 prefix[j+1] - prefix[i] 快速得到。五、逐步计算示例以 stones = [5,3,1,4,2] 为例，n=5。前缀和 prefix = [ 0,5,8,9,13,15 ] 初始化： dp[i][i] = 0 长度 = 2： [ 0,1]: sum[ 1,1]=3, left_ gain = 3 - dp[ 1][ 1 ]=3-0=3 sum[ 0,0]=5, right_ gain = 5 - dp[ 0][ 0 ]=5-0=5 dp[ 0][ 1 ] = max(3,5)=5 [ 1,2]: sum[ 2,2]=1, left_ gain=1-0=1 sum[ 1,1]=3, right_ gain=3-0=3 dp[ 1][ 2 ] = 3 [ 2,3]: sum[ 3,3]=4, left_ gain=4, sum[ 2,2]=1, right_ gain=1, dp[ 2][ 3 ]=4 [ 3,4]: sum[ 4,4]=2, left_ gain=2, sum[ 3,3]=4, right_ gain=4, dp[ 3][ 4 ]=4 长度 = 3： [ 0,2 ]: sum[ 1,2]=3+1=4, left_ gain = 4 - dp[ 1][ 2 ] = 4-3=1 sum[ 0,1]=5+3=8, right_ gain = 8 - dp[ 0][ 1 ] = 8-5=3 dp[ 0][ 2 ] = max(1,3)=3 [ 1,3 ]: sum[ 2,3]=1+4=5, left_ gain=5-dp[ 2][ 3 ]=5-4=1 sum[ 1,2]=3+1=4, right_ gain=4-dp[ 1][ 2 ]=4-3=1 dp[ 1][ 3 ] = 1 [ 2,4 ]: sum[ 3,4]=4+2=6, left_ gain=6-dp[ 3][ 4 ]=6-4=2 sum[ 2,3]=1+4=5, right_ gain=5-dp[ 2][ 3 ]=5-4=1 dp[ 2][ 4 ] = 2 长度 = 4： [ 0,3 ]: sum[ 1,3]=3+1+4=8, left_ gain=8-dp[ 1][ 3 ]=8-1=7 sum[ 0,2]=5+3+1=9, right_ gain=9-dp[ 0][ 2 ]=9-3=6 dp[ 0][ 3 ] = 7 [ 1,4 ]: sum[ 2,4]=1+4+2=7, left_ gain=7-dp[ 2][ 4 ]=7-2=5 sum[ 1,3]=3+1+4=8, right_ gain=8-dp[ 1][ 3 ]=8-1=7 dp[ 1][ 4 ] = 7 长度 = 5： [ 0,4 ]: sum[ 1,4]=3+1+4+2=10, left_ gain=10-dp[ 1][ 4 ]=10-7=3 sum[ 0,3]=5+3+1+4=13, right_ gain=13-dp[ 0][ 3 ]=13-7=6 dp[ 0][ 4 ] = max(3,6)=6 最终结果 = 6，与示例一致。六、时间复杂度与空间复杂度时间复杂度：O(n²)，n 为石子堆数，需要计算所有区间。空间复杂度：O(n²)，dp 表大小。可以优化到 O(n) 但实现稍复杂。七、总结石子游戏 VII 是典型的博弈类区间 DP ，关键点：定义 dp[i][j] 为当前玩家在区间 [i..j] 能获得的最大差值（自己得分 − 对手得分）。转移时，当前玩家取左或右，得到本次得分 = 剩余石子总和，然后减去对手在后续区间的最优差值（因为对手的得分会减少当前玩家的最终优势）。最终答案即 dp[0][n-1] 。该题在已知总和的情况下，利用前缀和快速计算剩余和，实现简洁高效。