石子游戏 VI（博弈类区间DP） 题目描述 Alice 和 Bob 轮流玩一个石子游戏，他们面前有一排石子堆，每堆石子有一个正整数权重。游戏规则如下： 玩家可以从当前剩余石子堆的 两端 中的任意一端取走一堆石子（即每次只能取最左边或最右边的那一堆）。 取走的石子堆的权重会计入该玩家的得分。 游戏持续到所有石子堆被取完。 两个玩家都采取 最优策略 ，且 Alice 先手。 目标是自己得分尽可能高，同时让对方得分尽可能低。 给定一个整数数组 stones ，表示石子堆的权重，请判断 Alice 是否能赢。如果 Alice 的得分严格大于 Bob 的得分，返回 true ；否则返回 false 。 解题过程 1. 问题分析 这是一个 零和博弈 问题，双方都采取最优策略。由于每次只能从两端取石子，问题可以转化为一个 区间动态规划 问题：用 dp[i][j] 表示当石子堆剩余为第 i 到第 j 堆时，当前玩家（不一定是 Alice）能比对手多得的分数（即当前玩家得分减去对手得分）。 2. 状态定义 设 dp[i][j] 表示当石子堆为 stones[i] 到 stones[j] 时，当前行动玩家能获得的最大相对优势（即当前玩家得分减去对手得分）。 3. 状态转移方程 当轮到当前玩家时，他有两种选择： 取左端石子堆 stones[i] ：此时他获得 stones[i] 分，然后轮到对手在区间 [i+1, j] 行动。对手在子区间 [i+1, j] 的相对优势是 dp[i+1][j] （对手得分减去当前玩家在子区间的得分）。因此，当前玩家取左端的相对优势为： stones[i] - dp[i+1][j] 取右端石子堆 stones[j] ：类似地，相对优势为： 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 ）时，当前玩家只能取这一堆，相对优势就是 stones[i] （因为对手得分为 0）： dp[i][i] = stones[i] 5. 计算顺序 由于 dp[i][j] 依赖于 dp[i+1][j] 和 dp[i][j-1] ，我们需要按区间长度从小到大计算： 先计算所有长度为 1 的区间 再计算长度为 2、3、...、n 的区间 6. 结果判断 最终，整个区间 [0, n-1] 的相对优势为 dp[0][n-1] 。如果 dp[0][n-1] > 0 ，说明 Alice 作为先手能获得比 Bob 更高的分数，返回 true ；否则返回 false 。 7. 示例验证 例： stones = [3, 5, 1, 7] 初始化： dp[0][0]=3 , dp[1][1]=5 , dp[2][2]=1 , dp[3][3]=7 长度 2： dp[0][1] = max(3-dp[1][1], 5-dp[0][0]) = max(3-5, 5-3) = max(-2, 2) = 2 dp[1][2] = max(5-1, 1-5) = max(4, -4) = 4 dp[2][3] = max(1-7, 7-1) = max(-6, 6) = 6 长度 3： dp[0][2] = max(3-dp[1][2], 1-dp[0][1]) = max(3-4, 1-2) = max(-1, -1) = -1 dp[1][3] = max(5-dp[2][3], 7-dp[1][2]) = max(5-6, 7-4) = max(-1, 3) = 3 长度 4： dp[0][3] = max(3-dp[1][3], 7-dp[0][2]) = max(3-3, 7-(-1)) = max(0, 8) = 8 结果 dp[0][3] = 8 > 0 ，返回 true 。 8. 复杂度分析 时间复杂度：O(n²)，需要填充 n×(n+1)/2 个状态 空间复杂度：O(n²)，用于存储 dp 表