预测赢家问题（数组非负版） 题目描述： 给定一个非负整数数组nums，两个玩家轮流从数组的任意一端取数。每次一个玩家只能从当前数组的起始位置或结束位置取一个数字，取到的数字累加到该玩家的得分中。当数组中没有数字时游戏结束。如果先手玩家的得分大于或等于后手玩家的得分，则先手玩家获胜；否则后手玩家获胜。假设两个玩家都采取最优策略，判断先手玩家是否能获胜。 解题过程： 问题分析 这是一个典型的零和博弈问题，我们可以使用区间动态规划来求解。关键思路是：对于当前玩家，在剩余区间[ i,j ]上，他能够获得的最大分数优势（即当前玩家得分减去对手得分的差值）。 状态定义 定义dp[ i][ j]表示当数组剩下区间[ i,j ]时，当前玩家（不一定是先手）能够比对手多得的分数。 状态转移方程 当i = j时，只有一个数字nums[ i]，当前玩家只能取这个数字，所以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 ]) 边界情况 当i > j时，区间为空，dp[ i][ j ] = 0 计算顺序 由于dp[ i][ j]依赖于dp[ i+1][ j]和dp[ i][ j-1 ]，我们需要按照区间长度从小到大的顺序计算： 先计算所有长度为1的区间 再计算长度为2的区间 依此类推，直到计算整个区间[ 0,n-1 ] 最终判断 如果dp[ 0][ n-1 ] ≥ 0，说明先手玩家能够获胜（得分大于或等于后手玩家）；否则后手玩家获胜。 举例说明： 对于数组[ 1,5,2 ]： dp[ 0][ 0] = 1, dp[ 1][ 1] = 5, dp[ 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] = max(1-dp[ 1][ 2], 2-dp[ 0][ 1 ]) = max(1-3, 2-4) = max(-2,-2) = -2 由于dp[ 0][ 2] = -2 < 0，所以先手玩家无法获胜。