区间动态规划例题：预测赢家问题（数组可能包含负数） 题目描述 给定一个整数数组nums，两个玩家轮流从数组的任意一端取数（每次只能取最左边或最右边的数字），取到的数字累加到自己的得分中。玩家A先手，玩家B后手。当数组被取完后，如果玩家A的得分大于等于玩家B的得分，则返回true，否则返回false。假设每个玩家都采取最优策略。注意：数组可能包含负数。 解题过程 问题分析 这是一个零和博弈问题，两个玩家轮流从数组两端取数，目标都是最大化自己的净胜分（自己的得分减去对手的得分）。 由于数组可能包含负数，传统的贪心策略（如总是取较大值）可能失效，因为需要全局考虑后续的得分影响。 区间动态规划适合解决这类问题，因为每一步操作都是在剩余数组的某个子区间上进行。 状态定义 定义 dp[i][j] 表示当数组剩余部分为子数组 nums[i..j] 时，当前行动玩家（不一定是玩家A）能比对手多得的分数。 注意： dp[i][j] 的值是从当前行动玩家的视角计算的净胜分。 状态转移方程 当轮到当前玩家行动时，他有两种选择： 取左端的数 nums[i] ：那么对手会在剩下的区间 [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 ]) \] 边界条件 当区间长度为1（即 i == j ）时，当前玩家只能取这一个数，所以 dp[i][i] = nums[i] 。 计算顺序 由于 dp[i][j] 依赖于 dp[i+1][j] 和 dp[i][j-1] ，我们需要从小区间到大区间进行计算。 具体地，按区间长度 len 从1到n（数组长度）遍历所有子数组。 结果判断 最终， dp[0][n-1] 表示玩家A先手时，能比玩家B多得的分数。 如果 dp[0][n-1] >= 0 ，说明玩家A的得分大于等于玩家B，返回true；否则返回false。 举例说明 以数组 nums = [1, 5, 2] 为例（虽无负数，但演示过程通用）： 初始化： dp[0][0]=1 , dp[1][1]=5 , dp[2][2]=2 。 长度2的区间： [0,1] ： dp[0][1] = max(1-dp[1][1], 5-dp[0][0]) = max(1-5, 5-1) = max(-4, 4) = 4 [1,2] ： dp[1][2] = max(5-dp[2][2], 2-dp[1][1]) = max(5-2, 2-5) = max(3, -3) = 3 长度3的区间 [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 ，所以玩家A会输，返回false。 关键点 状态定义中"当前玩家"是相对的，每一步的 dp[i][j] 都代表当前行动玩家的优势。 转移方程中的减法体现了零和博弈的对抗性：对手的收益就是你的损失。 即使数组包含负数，该模型依然适用，因为决策时会自动权衡正负数的全局影响。