区间动态规划例题：预测赢家问题 题目描述 给定一个非负整数数组nums，两个玩家轮流从数组的两端取数（每次只能取最左或最右端的数字），取到的数字就是该玩家的得分。双方都采取最优策略，如果先手玩家能获胜（即总得分大于或等于后手玩家），则返回true，否则返回false。假设数组长度不超过20。 解题思路 这个问题可以用区间动态规划解决。核心思想是定义dp[ i][ j]表示在子数组nums[ i..j ]上，当前行动的玩家（不一定是先手）能比对手多得的分数。通过比较最终差值是否>=0来判断先手是否获胜。 详细解题步骤 定义状态 定义dp[ i][ j]为当数组剩下部分为nums[ i]到nums[ 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 ]) 边界条件 当区间长度为1时（i = j），当前玩家只能取这个数，比对手多的分数就是这个数本身： dp[ i][ i] = nums[ i ] 计算顺序 由于dp[ i][ j]依赖于dp[ i+1][ j]和dp[ i][ j-1 ]，我们需要从小区间向大区间计算： 按区间长度len从1到n遍历 对于每个长度，遍历所有起始位置i 最终结果 dp[ 0][ n-1]表示在整个数组上，先手玩家比后手玩家多的分数。如果dp[ 0][ n-1 ] >= 0，则先手可以获胜。 示例分析 以nums = [ 1, 5, 2 ]为例： 初始化单个元素的区间： dp[ 0][ 0] = 1, dp[ 1][ 1] = 5, dp[ 2][ 2 ] = 2 计算长度为2的区间： [ 0,1]：max(1-dp[ 1][ 1], 5-dp[ 0][ 0 ]) = max(1-5, 5-1) = max(-4, 4) = 4 [ 1,2]：max(5-dp[ 2][ 2], 2-dp[ 1][ 1 ]) = max(5-2, 2-5) = max(3, -3) = 3 计算长度为3的区间[ 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数组，大小为n×n 按区间长度从小到大填充dp表 最终判断dp[ 0][ n-1 ] >= 0 这种方法的时间复杂度是O(n²)，空间复杂度是O(n²)，能够高效解决这个问题。