区间动态规划例题：预测赢家问题（数组可能包含负数） 题目描述 给定一个整数数组 nums，两个玩家轮流从数组的任意一端取走一个数字。每次取数字后，该数字会从数组中移除。游戏持续到数组为空为止。最终，每个玩家取得的数字总和就是他们的得分。如果先手玩家的得分大于或等于后手玩家的得分，则先手玩家获胜；否则，后手玩家获胜。 假设两位玩家都采取最优策略，判断先手玩家是否能获胜。 解题过程 问题分析 这是一个零和博弈问题，每个玩家都希望最大化自己的得分。 由于数组可能包含负数，玩家在选择时不仅要考虑获取较大的正数，还要避免将较大的负数留给对手。 这是一个区间动态规划问题，因为每一步的选择都会改变数组的区间范围。 状态定义 定义 dp[ i][ j] 表示当数组剩余部分为 nums[ i..j ] 时，当前玩家（不一定是先手）可以比对手多得的分数。 注意：这里的“当前玩家”是指当前轮到行动的玩家，而不是固定的先手或后手。 状态转移方程 当 i == j 时，只有一个数字，当前玩家只能取这个数字，所以 dp[ i][ j] = nums[ i ]。 当 i < j 时，当前玩家有两种选择： 取左端的数字 nums[ i]：那么对手会在区间 [ i+1, j] 上采取最优策略，当前玩家实际比对手多得的分数是 nums[ i] - dp[ i+1][ j ] 取右端的数字 nums[ j]：那么对手会在区间 [ 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的区间，dp[ i][ i] = nums[ i ] 计算顺序 我们需要按照区间长度从小到大的顺序计算 先计算所有长度为1的区间 然后计算长度为2的区间，接着是长度为3的区间，直到整个数组长度 结果判断 如果 dp[ 0][ n-1 ] >= 0，说明先手玩家可以获胜（得分大于或等于后手） 如果 dp[ 0][ n-1] < 0，说明先手玩家会输 示例演示 以数组 [ 1, 5, 2 ] 为例： 初始化长度为1的区间： 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，先手玩家会输 算法实现要点 时间复杂度：O(n²)，需要填充 n×(n+1)/2 个状态 空间复杂度：O(n²)，需要一个 n×n 的DP表 对于包含负数的数组，算法同样适用，因为状态转移方程已经考虑了负数的影响 可以使用滚动数组优化空间复杂度到 O(n)