区间动态规划例题：预测赢家问题（数组非负版） 题目描述 给定一个非负整数数组 nums ，两名玩家轮流从数组的任意一端取数（每次只能取最左或最右的元素），取完后该元素从数组中移除。游戏结束当所有元素被取完。每位玩家的分数是他所取数字的总和。假设两名玩家都采用最优策略，如果先手玩家的分数不小于后手玩家的分数，则返回 true ，否则返回 false 。 示例 输入： nums = [1, 5, 2] 输出： false 解释：先手玩家一开始可以选 1 或 2： 若选 1，后手玩家可以选 5（剩余 [ 5, 2 ] 中选较大值），后手胜； 若选 2，后手玩家选 5（剩余 [ 1, 5 ] 中选较大值），后手胜。 解题步骤 1. 问题分析 这是一个零和博弈问题，双方均采取最优策略。 关键点：在任意子数组 nums[i...j] 上，当前玩家能获得的 净胜分 （当前玩家得分减去对手得分）是多少。 若净胜分 ≥ 0，则当前玩家在该子数组上必胜或平局。 2. 定义状态 设 dp[i][j] 表示当数组剩余部分为 nums[i...j] 时， 当前行动玩家 能比对手多得的分数（即净胜分）。 注意： dp[i][j] 的定义是 当前玩家 （不一定是先手）的净胜分。 3. 状态转移 当前玩家有两种选择： 取左端 nums[i] ：此时对手会在子数组 nums[i+1...j] 上行动，对手的净胜分为 dp[i+1][j] （对手作为当前玩家）。因此当前玩家的净胜分为： 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]) 4. 边界条件 当 i == j 时，只剩一个数字，当前玩家取走它，净胜分为 nums[i] ： dp[i][i] = nums[i] 5. 计算顺序 区间动态规划通常按区间长度从小到大计算。 外层循环：区间长度 len 从 1 到 n 内层循环：左端点 i 从 0 到 n-len ，计算右端点 j = i+len-1 6. 最终结果 初始时整个数组 nums[0...n-1] 的当前玩家是先手，所以若 dp[0][n-1] >= 0 则先手必胜或平局，返回 true 。 示例推导（nums = [ 1, 5, 2]） 初始化单元素区间： dp[0][0] = 1 dp[1][1] = 5 dp[2][2] = 2 计算长度为 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 计算整个数组 dp[0][2] ： 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 ，先手必输，返回 false 。 复杂度分析 时间复杂度：O(n²)，需要填充 n×(n+1)/2 个状态。 空间复杂度：O(n²)，可用滚动数组优化至 O(n)。