区间动态规划例题：预测赢家问题 题目描述 给定一个非负整数数组 nums 。两个玩家轮流从数组的任意一端（即 nums[0] 或 nums[nums.length-1] ）取走一个数字。取走数字后，该数字被从数组中移除。游戏持续进行，直到数组为空。最终，拿到数字总和最大的玩家获胜。 假设两位玩家都采用最佳策略进行游戏。如果先手玩家能获胜，则返回 true ；否则，返回 false 。 示例 1: 输入: nums = [ 1, 5, 2 ] 输出: false 解释: 先手玩家开始时可以拿 1 或 2。 如果他拿 2，那么数组变成 [ 1, 5 ]。后手玩家可以拿 5（总和=5），然后先手玩家拿 1（总和=1），先手总分为 1+2=3，后手总分为5，后手胜。 如果他拿 1，那么数组变成 [ 5, 2 ]。后手玩家可以拿 5（总和=5），然后先手玩家拿 2（总和=2），先手总分为 1+2=3，后手总分为5，后手胜。 所以，先手玩家无论如何都会输，返回 false。 示例 2: 输入: nums = [ 1, 5, 233, 7 ] 输出: true 解释: 先手玩家第一次拿 1。然后数组变成 [ 5, 233, 7 ]。无论后手玩家拿 5 还是 7，先手玩家之后都可以拿 233，从而确保胜利。 解题过程 问题分析与状态定义 这个问题属于“零和博弈”，即一方的收益等于另一方的损失。我们可以将问题转化为：计算先手玩家在某个子数组上能比后手玩家多获得多少分数。如果最终在整个数组上，先手比后手多的分数 >= 0，则先手获胜（或至少不败，题目通常要求严格获胜才为 true，但多0分也视为平局，根据题意，若平局则先手也算获胜，因为题目是“拿到数字总和最大”，平局时先手并未输）。 我们使用一个二维数组 dp 来存储子问题的结果。 状态定义 ：令 dp[i][j] 表示当数组剩下部分为 nums[i], nums[i+1], ..., nums[j] 时，当前行动的玩家（不一定是先手，而是轮到谁行动）能比对方多获得的最大分数。 目标 ：我们需要计算 dp[0][n-1] 的值。如果 dp[0][n-1] >= 0 ，则先手玩家可以获胜或不败（根据题目具体描述，通常 >=0 即返回 true）。 状态转移方程 考虑一个子数组 nums[i..j] 。 如果当前轮到你先手（即当前行动的玩家是“先手”角色）： 如果你选择拿左端的数字 nums[i] ，那么你立刻获得 nums[i] 的分数。接下来，在子数组 nums[i+1..j] 上，轮到对方先手。根据 dp 的定义， dp[i+1][j] 表示在子数组 [i+1, j] 上，当前行动者（此时是对方）能比对方（此时是你）多获得的分数。因此，你拿 nums[i] 后，你相对于对方的总分数优势为： nums[i] - dp[i+1][j] 。 如果你选择拿右端的数字 nums[j] ，同理，你相对于对方的总分数优势为： nums[j] - dp[i][j-1] 。 因为你们都采取最佳策略，你肯定会选择能使自己相对优势最大化的操作。所以： dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]) 这个方程巧妙地统一了先手和后手的视角。 dp[i][j] 始终表示当前行动者的相对优势。当你在 [i, j] 上行动时，你拿分，然后减去对方在剩下区间上行动时的相对优势（因为对方行动时，优势在他那边），就得到了你的净优势。 边界条件 当子数组长度为 1，即 i == j 时，数组只剩下一个数字 nums[i] 。当前行动者只能拿这个数字，对方得分为0。所以当前行动者的相对优势就是 nums[i] 。 即： dp[i][i] = nums[i] 。 计算顺序 由于计算 dp[i][j] 依赖于 dp[i+1][j] （左边更短的区间）和 dp[i][j-1] （右边更短的区间），我们需要按照子数组的长度 L 从小到大进行遍历。 首先遍历所有长度为 1 的子数组（ L = 0 ，即 i == j ）。 然后遍历长度为 2 的子数组（ L = 1 ，即 j = i+1 ）。 接着是长度为 3 的子数组（ L = 2 ，即 j = i+2 ）。 ... 最后计算整个数组 L = n-1 （即 i=0, j=n-1 ）。 最终结果 计算完整个 dp 表后， dp[0][n-1] 表示在初始数组 nums[0..n-1] 上，先手玩家能比后手玩家多获得的分数。 如果 dp[0][n-1] >= 0 ，返回 true （先手获胜或至少不败）。 如果 dp[0][n-1] < 0 ，返回 false （先手失败）。 逐步计算示例 (nums = [ 1, 5, 2]) 初始化 ： n = 3 dp[0][0] = 1 dp[1][1] = 5 dp[2][2] = 2 计算长度为 2 的子数组 (L=1) [0,1] : dp[0][1] = max(nums[0] - dp[1][1], nums[1] - dp[0][0]) = max(1-5, 5-1) = max(-4, 4) = 4 [1,2] : dp[1][2] = max(nums[1] - dp[2][2], nums[2] - dp[1][1]) = max(5-2, 2-5) = max(3, -3) = 3 计算整个数组 (L=2, [ 0,2]) dp[0][2] = max(nums[0] - dp[1][2], nums[2] - dp[0][1]) = max(1-3, 2-4) = max(-2, -2) = -2 判断结果 dp[0][2] = -2 < 0 ，所以先手玩家会输，返回 false 。这与题目示例一致。 通过这个循序渐进的推导，我们可以看到区间动态规划如何清晰地模拟游戏过程，并通过子问题的解来构建原问题的解。