486. 预测赢家

🟠   🔖  递归 数组 数学 动态规划 博弈  🔗 力扣 LeetCode

题目

You are given an integer array nums. Two players are playing a game with this array: player 1 and player 2.

Player 1 and player 2 take turns, with player 1 starting first. Both players start the game with a score of 0. At each turn, the player takes one of the numbers from either end of the array (i.e., nums[0] or nums[nums.length - 1]) which reduces the size of the array by 1. The player adds the chosen number to their score. The game ends when there are no more elements in the array.

Return true if Player 1 can win the game. If the scores of both players are equal, then player 1 is still the winner, and you should also return true. You may assume that both players are playing optimally.

Example 1:

Input: nums = [1,5,2]

Output: false

Explanation: Initially, player 1 can choose between 1 and 2.

If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2).

So, final score of player 1 is 1 + 2 = 3, and player 2 is 5.

Hence, player 1 will never be the winner and you need to return false.

Example 2:

Input: nums = [1,5,233,7]

Output: true

Explanation: Player 1 first chooses 1. Then player 2 has to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233.

Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.

Constraints:

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 10^7

题目大意

给你一个整数数组 nums 。玩家 1 和玩家 2 基于这个数组设计了一个游戏。

玩家 1 和玩家 2 轮流进行自己的回合，玩家 1 先手。开始时，两个玩家的初始分值都是 0 。每一回合，玩家从数组的任意一端取一个数字（即，nums[0] 或 nums[nums.length - 1]），取到的数字将会从数组中移除（数组长度减 1 ）。玩家选中的数字将会加到他的得分上。当数组中没有剩余数字可取时，游戏结束。

如果玩家 1 能成为赢家，返回 true 。如果两个玩家得分相等，同样认为玩家 1 是游戏的赢家，也返回 true 。你可以假设每个玩家的玩法都会使他的分数最大化。

示例 1：

输入： nums = [1,5,2]

输出： false

解释： 一开始，玩家 1 可以从 1 和 2 中进行选择。

如果他选择 2（或者 1 ），那么玩家 2 可以从 1（或者 2 ）和 5 中进行选择。如果玩家 2 选择了 5 ，那么玩家 1 则只剩下 1（或者 2 ）可选。

所以，玩家 1 的最终分数为 1 + 2 = 3，而玩家 2 为 5 。

因此，玩家 1 永远不会成为赢家，返回 false 。

示例 2：

输入： nums = [1,5,233,7]

输出： true

解释： 玩家 1 一开始选择 1 。然后玩家 2 必须从 5 和 7 中进行选择。无论玩家 2 选择了哪个，玩家 1 都可以选择 233 。

最终，玩家 1（234 分）比玩家 2（12 分）获得更多的分数，所以返回 true，表示玩家 1 可以成为赢家。

提示：

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 10^7

解题思路

你的 predictTheWinner 实现采用的是 动态规划 (DP) 方法，利用 区间 DP 来计算玩家 1 和玩家 2 的最大得分差值。
这个方法的核心思想是：当前玩家的得分 = 选取的数字 - 剩下部分的最优策略得分。

1. 定义状态 dp[i][j]

• dp[i][j] 表示 当前玩家 在选择 nums[i:j] 这段子数组时，比对手多获得的分数。
• 如果 dp[0][n-1] >= 0，说明玩家 1 至少不会输，返回 true，否则返回 false。

2. 状态转移方程

• 玩家 可以选择 nums[i] 或 nums[j]，然后 轮到对手 继续玩：
  • 选择 nums[i]，则收益 = nums[i] - dp[i+1][j]（对手会在 nums[i+1:j] 里采取最优策略）
  • 选择 nums[j]，则收益 = nums[j] - dp[i][j-1]（对手会在 nums[i:j-1] 里采取最优策略）
  • 取 最优选择： dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1])

3. 初始化

• 当 i == j 时，即子数组只剩一个元素，当前玩家的得分就是 nums[i]：dp[i][i] = nums[i]

4. 计算顺序

• dp[i][j] 依赖 dp[i+1][j] 和 dp[i][j-1]，所以需要从小区间递推到大区间：
  • 先遍历 区间长度 len，从 1 到 n-1
  • 然后 从左往右遍历起点 i，计算 dp[i][j]

复杂度分析

• 时间复杂度：O(n^2)，因为有两个嵌套循环。
• 空间复杂度：O(n^2)，由于使用了 dp 矩阵。

代码

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var predictTheWinner = function (nums) {
	const n = nums.length;
	let dp = new Array(n).fill().map(() => new Array(n).fill(0));
	for (let i = 0; i < n; i++) {
		dp[i][i] = nums[i];
	}
	for (let len = 1; len < n; len++) {
		for (let i = 0; i < n - len; i++) {
			const j = i + len;
			dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
		}
	}

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

相关题目

题号	标题	题解	标签	难度	力扣
464	我能赢吗	[✓]	位运算 记忆化搜索 数学 3+	🟠	🀄️ 🔗
3222	求出硬币游戏的赢家		数学 博弈 模拟	🟢	🀄️ 🔗
3238	求出胜利玩家的数目		数组 哈希表 计数	🟢	🀄️ 🔗
3320	统计能获胜的出招序列数		字符串 动态规划	🔴	🀄️ 🔗