这道题是典型的零和博弈 区间 DP。核心在于定义状态为“当前玩家能比对手多拿多少分”而不是各自拿了多少分——这样就能把双方的最优选择统一成一个取最大值的式子。方法一区间 DP推荐写法class Solution {public boolean predictTheWinner(int[] nums) {int n nums.length;// dp[i][j] 表示在子数组 nums[i…j] 上当前行动者能比对手多拿的分数int[][] dp new int[n][n];// 长度为 1只能拿自己 for (int i 0; i n; i) { dp[i][i] nums[i]; } // 从短区间往长区间推 for (int len 2; len n; len) { for (int i 0; i n - len; i) { int j i len - 1; int takeLeft nums[i] - dp[i 1][j]; // 拿左端剩下对手领先 dp[i1][j] int takeRight nums[j] - dp[i][j - 1]; // 拿右端 dp[i][j] Math.max(takeLeft, takeRight); } } return dp[0][n - 1] 0; // 先手不输就算赢 }}方法二空间优化到 O(n)观察转移只依赖 dp[i1][j]下一行和 dp[i][j-1]左边可以压成一维class Solution {public boolean predictTheWinner(int[] nums) {int n nums.length;int[] dp new int[n];for (int i n - 1; i 0; i--) { dp[i] nums[i]; // len 1 for (int j i 1; j n; j) { dp[j] Math.max(nums[i] - dp[j], // 拿左端dp[j] 还是上一轮的 dp[i1][j] nums[j] - dp[j - 1]); // 拿右端 } } return dp[n - 1] 0; }}方法三记忆化搜索思路最直观class Solution {private Integer[][] memo;private int[] nums;public boolean predictTheWinner(int[] nums) { this.nums nums; this.memo new Integer[nums.length][nums.length]; return dfs(0, nums.length - 1) 0; } private int dfs(int i, int j) { if (i j) return nums[i]; if (memo[i][j] ! null) return memo[i][j]; int takeLeft nums[i] - dfs(i 1, j); int takeRight nums[j] - dfs(i, j - 1); return memo[i][j] Math.max(takeLeft, takeRight); }}复杂度维度 复杂度时间 O(n²)共 n²/2 个状态每个 O(1)空间 O(n²) / O(n) / O(n²)递归栈 O(n)面试易错点状态定义成“先手能拿到的最大总分”会很难转移因为轮到谁在变。定义成分差对手的领先就是自己的落后直接取负即可这是这类博弈题的通用技巧。边界条件是 0 而不是 0题目规定平局也算先手赢。填表顺序必须是区间从小到大或 i 从大到小、j 从小到大否则子问题还没算出来。别用贪心每次挑两端里大的那个是错的反例 [1, 5, 233, 7]贪心拿 7 会输。加分项当数组长度为偶数时先手可以强制拿走所有奇数位或所有偶数位的元素因此偶数长度时先手必不败可直接返回 true。这个结论能在面试中体现数学直觉但写代码时加上要说明理由。这道题和 LeetCode 877. 石子游戏 几乎一样877 保证偶数长度且总数为奇数所以答案恒为 true另外 LeetCode 1406. 石子游戏 III 也是同样的“分差 DP”套路只是变成了一维后缀。把这三题放在一起刷博弈类 DP 基本就通了。要不要我接着为你讲解 LeetCode 877. 石子游戏的 Java 实现
