这道题是典型的零和博弈 + 区间 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[i+1][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[i+1][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[i+1][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 实现？
