区间动态规划例题：预测赢家问题 题目描述 给定一个非负整数数组 nums ，两名玩家轮流从数组的 两端 （即第一个或最后一个元素）取数，每次取一个数字，取走后数字被移除。玩家每次只能取两端的数字，不能取中间的数字。最终取的数字总和最多的玩家获胜。假设两名玩家都采取 最优策略 ，判断先手玩家是否能获胜（或先手玩家的得分是否大于等于后手玩家）。例如： 输入： [1, 5, 2] 输出： False （先手取1或2，后手总能取到5，先手输）。 解题过程 步骤1：定义状态 用 dp[i][j] 表示在子数组 nums[i..j] 中， 先手玩家 能比后手玩家 多得的分数 （注意：这里“先手”指的是当前轮次首先行动的一方，不一定是全局的先手）。 若 dp[0][n-1] >= 0 ，则全局先手玩家能获胜。 步骤2：状态转移 当 i == j 时，只有一个数字，先手直接取走，后手无数字可取。因此 dp[i][j] = nums[i] 。 当 i < j 时，先手有两种选择： 取左端 nums[i] ：后手变为子数组 nums[i+1..j] 的先手，先手在此轮比后手多 nums[i] - dp[i+1][j] 。 取右端 nums[j] ：后手变为子数组 nums[i..j-1] 的先手，先手多 nums[j] - dp[i][j-1] 。 最优策略下，先手会选择最大化自己优势的方案： dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]) 。 步骤3：计算顺序 区间长度 len 从 1 到 n （数组长度）递增计算，确保计算 dp[i][j] 时，更短的区间 dp[i+1][j] 和 dp[i][j-1] 已计算。 步骤4：示例演算 以 nums = [1, 5, 2] 为例： 初始化单元素区间： dp[0][0] = 1 , dp[1][1] = 5 , dp[2][2] = 2 。 长度 len = 2 ： dp[0][1] = max(1 - dp[1][1], 5 - dp[0][0]) = max(1-5, 5-1) = max(-4, 4) = 4 。 dp[1][2] = max(5 - dp[2][2], 2 - dp[1][1]) = max(5-2, 2-5) = max(3, -3) = 3 。 长度 len = 3 ： dp[0][2] = max(1 - dp[1][2], 2 - dp[0][1]) = max(1-3, 2-4) = max(-2, -2) = -2 。 结果： dp[0][2] = -2 < 0 ，先手输。 关键点 通过差值 dp[i][j] 将博弈问题转化为最优化子问题，避免分别记录两名玩家的分数。 区间DP通过逐步扩展区间长度，覆盖所有可能的游戏状态。