石子游戏 VII（博弈类区间DP） 题目描述： 有一排石子堆排成一行，每个石子堆有一个对应的价值数组 stones，其中 stones[ i ] 表示第 i 堆石子的价值。两名玩家（Alice 和 Bob）轮流进行游戏，Alice 先手。在每一轮中，玩家可以从当前剩余石子堆的最左端或最右端移除一堆石子，并获得相应的分数。玩家的得分是他移除石子堆价值的总和。游戏的目标是最大化自己的得分差值。假设两位玩家都采用最优策略，请返回 Alice 能够取得的最高得分差值。 解题过程： 我们使用动态规划来解决这个问题。定义 dp[ i][ j] 表示当剩余石子堆为 stones[ i...j ] 时，当前玩家（不一定是 Alice）可以比对手多得的分数。 状态转移方程： 当轮到当前玩家时，他有两种选择： 移除最左边的石子堆 stones[ i]，那么他会获得 stones[ i] 的分数，然后轮到对手在 stones[ i+1...j] 上操作。此时对手会比当前玩家多 dp[ i+1][ j] 分，所以当前玩家比对手多 stones[ i] - dp[ i+1][ j ] 分。 移除最右边的石子堆 stones[ j]，那么他会获得 stones[ j] 的分数，然后轮到对手在 stones[ i...j-1] 上操作。此时对手会比当前玩家多 dp[ i][ j-1] 分，所以当前玩家比对手多 stones[ j] - dp[ i][ j-1 ] 分。 由于当前玩家会选择对自己更有利的操作，所以： dp[ i][ j] = max(stones[ i] - dp[ i+1][ j], stones[ j] - dp[ i][ j-1 ]) 边界条件： 当 i = j 时，即只剩下一堆石子，当前玩家移除它，获得 stones[ i] 分，对手得 0 分，所以 dp[ i][ i] = stones[ i ]。 具体步骤： 初始化一个 n×n 的 dp 数组，其中 n 是石子堆的数量。 按区间长度从小到大进行遍历： 长度为 1：dp[ i][ i] = stones[ i ] 长度从 2 到 n： 对于每个起始位置 i，计算结束位置 j = i + len - 1 dp[ i][ j] = max(stones[ i] - dp[ i+1][ j], stones[ j] - dp[ i][ j-1 ]) 最终结果存储在 dp[ 0][ n-1 ] 中，表示 Alice 先手时能比 Bob 多得的分数。 示例验证： 假设 stones = [ 5,3,1,4,2 ] 计算过程： 长度为1：dp[ 0][ 0]=5, dp[ 1][ 1]=3, dp[ 2][ 2]=1, dp[ 3][ 3]=4, dp[ 4][ 4 ]=2 长度为2： dp[ 0][ 1] = max(5-dp[ 1][ 1], 3-dp[ 0][ 0 ]) = max(5-3, 3-5) = max(2,-2) = 2 dp[ 1][ 2 ] = max(3-1, 1-3) = max(2,-2) = 2 dp[ 2][ 3 ] = max(1-4, 4-1) = max(-3,3) = 3 dp[ 3][ 4 ] = max(4-2, 2-4) = max(2,-2) = 2 长度为3： dp[ 0][ 2] = max(5-dp[ 1][ 2], 1-dp[ 0][ 1 ]) = max(5-2, 1-2) = max(3,-1) = 3 dp[ 1][ 3] = max(3-dp[ 2][ 3], 4-dp[ 1][ 2 ]) = max(3-3, 4-2) = max(0,2) = 2 dp[ 2][ 4] = max(1-dp[ 3][ 4], 2-dp[ 2][ 3 ]) = max(1-2, 2-3) = max(-1,-1) = -1 长度为4： dp[ 0][ 3] = max(5-dp[ 1][ 3], 4-dp[ 0][ 2 ]) = max(5-2, 4-3) = max(3,1) = 3 dp[ 1][ 4] = max(3-dp[ 2][ 4], 2-dp[ 1][ 3 ]) = max(3-(-1), 2-2) = max(4,0) = 4 长度为5： dp[ 0][ 4] = max(5-dp[ 1][ 4], 2-dp[ 0][ 3 ]) = max(5-4, 2-3) = max(1,-1) = 1 最终 Alice 能比 Bob 多得 1 分。 这个解法的时间复杂度是 O(n²)，空间复杂度也是 O(n²)，通过自底向上的方式填充 dp 表，确保了我们能够正确计算每个子区间的最优解。