LeetCode 486. 预测赢家

Categories:

题目描述
思路分析
1. 解法一：区间动态规划（推荐）
相似题目

题目描述

✅ 486. 预测赢家

思路分析

解法一：区间动态规划（推荐）

核心思路：

设 dp[i][j] 表示当前玩家在区间 [i, j] 内能取得的最大净胜分（当前玩家分数减去对手分数）。

选择左端或右端，分别得到 nums[i] - dp[i+1][j] 与 nums[j] - dp[i][j-1]。

取最大值作为 dp[i][j]，最终 dp[0][n-1] >= 0 则先手可赢或平局。

复杂度分析：

时间复杂度：O(n^2)，其中 n 表示数组长度。

空间复杂度：O(n^2)，其中 n 表示数组长度。

class Solution {
    public boolean predictTheWinner(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n][n];

        for (int i = n - 1; i >= 0; i--) {
            dp[i][i] = nums[i];
            for (int j = i + 1; j < n; j++) {
                int pickLeft = nums[i] - dp[i + 1][j];
                int pickRight = nums[j] - dp[i][j - 1];
                dp[i][j] = Math.max(pickLeft, pickRight);
            }
        }

        return dp[0][n - 1] >= 0;
    }
}

func predictTheWinner(nums []int) bool {
	n := len(nums)
	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, n)
	}

	for i := n - 1; i >= 0; i-- {
		dp[i][i] = nums[i]
		for j := i + 1; j < n; j++ {
			pickLeft := nums[i] - dp[i+1][j]
			pickRight := nums[j] - dp[i][j-1]
			if pickLeft > pickRight {
				dp[i][j] = pickLeft
			} else {
				dp[i][j] = pickRight
			}
		}
	}

	return dp[0][n-1] >= 0
}

相似题目

题目	难度	考察点
877. 石子游戏	中等	博弈、动态规划
1140. 石子游戏 II	中等	博弈、动态规划
1406. 石子游戏 III	困难	博弈、动态规划
464. 我能赢吗	中等	博弈、记忆化搜索
1025. 除数博弈	简单	博弈、数学

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/29945168