石子游戏 VI（博弈类区间DP） 题目描述： Alice 和 Bob 轮流玩一个石子游戏，面前有一排石子堆，每个石子堆有一个正整数权重值。游戏规则如下： 玩家可以从当前剩余石子堆的两端（最左或最右）中选择一堆石子移除 当玩家移除石子堆时，获得该堆的权重值作为分数 游戏进行到所有石子堆都被移除为止 两个玩家都采取最优策略，Alice 先手 问题：假设石子堆的权重数组为 stones，请计算如果 Alice 和 Bob 都采取最优策略，Alice 最终能比 Bob 多多少分。 解题过程： 步骤1：问题分析 这是一个典型的博弈类区间动态规划问题。我们需要计算在区间 [ i, j ] 上，当前玩家能比对手多得的最大分数。 步骤2：状态定义 定义 dp[ i][ j ] 表示当石子堆剩下从第 i 堆到第 j 堆时，当前玩家能比对手多得的最大分数。 步骤3：状态转移方程 对于区间 [ i, j ]，当前玩家有两种选择： 取左边的石子堆 stones[ i]，那么对手会在区间 [ i+1, j ] 上采取最优策略，当前玩家比对手多得的分数为： stones[ i] - dp[ i+1][ j ] 取右边的石子堆 stones[ j]，那么对手会在区间 [ 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 ]) 步骤4：边界条件 当区间长度为 1 时（即 i = j），当前玩家只能取这一堆： dp[ i][ i] = stones[ i ] 步骤5：计算顺序 我们需要按照区间长度从小到大的顺序计算： 先计算所有长度为 1 的区间 然后计算长度为 2 的区间 接着计算长度为 3 的区间 依此类推，直到计算整个区间 [ 0, n-1 ] 步骤6：示例演示 假设 stones = [ 3, 7, 2, 3 ] 初始化： dp[ 0][ 0 ] = 3 dp[ 1][ 1 ] = 7 dp[ 2][ 2 ] = 2 dp[ 3][ 3 ] = 3 计算长度为 2 的区间： dp[ 0][ 1] = max(3 - dp[ 1][ 1], 7 - dp[ 0][ 0 ]) = max(3-7, 7-3) = max(-4, 4) = 4 dp[ 1][ 2] = max(7 - dp[ 2][ 2], 2 - dp[ 1][ 1 ]) = max(7-2, 2-7) = max(5, -5) = 5 dp[ 2][ 3] = max(2 - dp[ 3][ 3], 3 - dp[ 2][ 2 ]) = max(2-3, 3-2) = max(-1, 1) = 1 计算长度为 3 的区间： dp[ 0][ 2] = max(3 - dp[ 1][ 2], 2 - dp[ 0][ 1 ]) = max(3-5, 2-4) = max(-2, -2) = -2 dp[ 1][ 3] = max(7 - dp[ 2][ 3], 3 - dp[ 1][ 2 ]) = max(7-1, 3-5) = max(6, -2) = 6 计算整个区间 [ 0, 3 ]： dp[ 0][ 3] = max(3 - dp[ 1][ 3], 3 - dp[ 0][ 2 ]) = max(3-6, 3-(-2)) = max(-3, 5) = 5 最终结果：Alice 能比 Bob 多得 5 分。 步骤7：算法实现要点 使用二维数组 dp，大小为 n × n 初始化对角线元素 dp[ i][ i] = stones[ i ] 按区间长度 len 从 2 到 n 循环 对于每个区间 [ i, j ]，其中 j = i + len - 1 根据状态转移方程计算 dp[ i][ j ] 这个解法的时间复杂度是 O(n²)，空间复杂度是 O(n²)，可以通过滚动数组优化到 O(n)。