石子游戏 VII（博弈类区间DP） 题目描述： Alice 和 Bob 轮流进行游戏，Alice 先手。有一排石子堆，每堆石子对应一个价值。玩家在每一轮可以从当前剩余石子堆的最左端或最右端取走一堆石子。游戏持续到所有石子堆都被取完。每个玩家的得分为其取走的石子堆价值之和。假设两位玩家都采用最优策略，请计算 Alice 能够赢得的最大分数差（即 Alice 得分 - Bob 得分）。 解题过程： 问题分析： 这是一个博弈类区间动态规划问题 每次只能从两端取石子，决策会影响后续状态 需要计算在最优策略下的最大分数差 状态定义： 定义 dp[ i][ j ] 表示当石子堆为从第 i 堆到第 j 堆时，当前玩家（不一定是Alice）能获得的最大分数差。 状态转移方程： 对于区间 [ i, j ]，当前玩家有两种选择： 取左端石子堆：得分 = stones[ i] - dp[ i+1][ j ] （当前获得stones[ i]，但接下来是对手的回合，对手会获得dp[ i+1][ j ]的分数差） 取右端石子堆：得分 = stones[ j] - dp[ i][ j-1 ] 因此状态转移方程为： dp[ i][ j] = max(stones[ i] - dp[ i+1][ j], stones[ j] - dp[ i][ j-1 ]) 边界条件： 当 i = j 时，只有一个石子堆，当前玩家直接取走： dp[ i][ i] = stones[ i ] 计算顺序： 由于区间动态规划通常按区间长度从小到大计算： 先计算长度为1的区间 再计算长度为2的区间 依此类推，直到计算整个区间[ 0, n-1 ] 最终结果： dp[ 0][ n-1 ] 就是 Alice 先手时能获得的最大分数差 示例演示： 假设石子堆为 [ 3, 7, 2, 5 ] 计算过程： 长度为1：dp[ 0][ 0]=3, dp[ 1][ 1]=7, dp[ 2][ 2]=2, dp[ 3][ 3 ]=5 长度为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], 5-dp[ 2][ 2 ]) = max(2-5, 5-2) = max(-3, 3) = 3 长度为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], 5-dp[ 1][ 2 ]) = max(7-3, 5-5) = max(4, 0) = 4 长度为4： dp[ 0][ 3] = max(3-dp[ 1][ 3], 5-dp[ 0][ 2 ]) = max(3-4, 5-(-2)) = max(-1, 7) = 7 最终 Alice 能获得的最大分数差为 7。