464. 我能赢吗

🟠   🔖  位运算 记忆化搜索 数学 动态规划 状态压缩 博弈  🔗 力扣 LeetCode

题目

In the "100 game" two players take turns adding, to a running total, any integer from 1 to 10. The player who first causes the running total to reach or exceed 100 wins.

What if we change the game so that players cannot re-use integers?

For example, two players might take turns drawing from a common pool of numbers from 1 to 15 without replacement until they reach a total >= 100.

Given two integers maxChoosableInteger and desiredTotal, return true if the first player to move can force a win, otherwise, return false. Assume both players play optimally.

Example 1:

Input: maxChoosableInteger = 10, desiredTotal = 11

Output: false

Explanation:

No matter which integer the first player choose, the first player will lose.

The first player can choose an integer from 1 up to 10.

If the first player choose 1, the second player can only choose integers from 2 up to 10.

The second player will win by choosing 10 and get a total = 11, which is >= desiredTotal.

Same with other integers chosen by the first player, the second player will always win.

Example 2:

Input: maxChoosableInteger = 10, desiredTotal = 0

Output: true

Example 3:

Input: maxChoosableInteger = 10, desiredTotal = 1

Output: true

Constraints:

• 1 <= maxChoosableInteger <= 20
• 0 <= desiredTotal <= 300

题目大意

在 "100 game" 这个游戏中，两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，先使得累计整数和 达到或超过 100 的玩家，即为胜者。

如果我们将游戏规则改为 “玩家 不能 重复使用整数” 呢？

例如，两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。

给定两个整数 maxChoosableInteger （整数池中可选择的最大数）和 desiredTotal（累计和），若先出手的玩家能稳赢则返回 true ，否则返回 false 。假设两位玩家游戏时都表现 最佳 。

示例 1：

输入： maxChoosableInteger = 10, desiredTotal = 11

输出： false

解释： 无论第一个玩家选择哪个整数，他都会失败。

第一个玩家可以选择从 1 到 10 的整数。

如果第一个玩家选择 1，那么第二个玩家只能选择从 2 到 10 的整数。

第二个玩家可以通过选择整数 10（那么累积和为 11 >= desiredTotal），从而取得胜利.

同样地，第一个玩家选择任意其他整数，第二个玩家都会赢。

示例 2:

输入： maxChoosableInteger = 10, desiredTotal = 0

输出： true

示例 3:

输入： maxChoosableInteger = 10, desiredTotal = 1

输出： true

提示:

• 1 <= maxChoosableInteger <= 20
• 0 <= desiredTotal <= 300

解题思路

本题涉及状态搜索和记忆化搜索，可以使用递归 + 备忘录 (Memoization) 来优化搜索过程。

1. 基本情况剪枝：

   • 如果 desiredTotal <= maxChoosableInteger，先手直接取 desiredTotal 胜利，返回 true。
   • 如果 sum(1, ..., maxChoosableInteger) < desiredTotal，则无论如何都无法达到目标，返回 false。
   • 如果 sum(1, ..., maxChoosableInteger) == desiredTotal，则取决 maxChoosableInteger 的奇偶性，正好取完所有数字的一方获胜。

2. 状态表示：

   • 使用一个 used 位标记哪些数字已被选过（可以用 bitmask）。
   • 递归检查当前状态下，是否存在某个选择可以导致对手必败。

3. 递归定义：

   • 设 canWin(used, total) 表示当前 used 状态下，当前玩家 是否有必胜策略：
     • 遍历所有未选过的数字 i：
       • 如果 i + total >= desiredTotal，当前玩家直接获胜。
       • 否则，对手进入 canWin(used | (1 << i), total + i) 状态：
         • 如果对手 必败，则当前玩家必胜。

4. 记忆化搜索：

   • 使用 Map 存储已计算过的 used 状态，避免重复搜索，提高效率。

复杂度分析

• 时间复杂度：O(m * 2^m)，其中 m = maxChoosableInteger，最坏情况下 m ≤ 20，仍然可行。
  • 状态数：2^m，即二进制掩码的不同状态。
  • 每次递归遍历 O(m)。
• 空间复杂度：O(m)，使用了一个哈希表存储 used 状态，避免重复计算。

代码

/**
 * @param {number} maxChoosableInteger
 * @param {number} desiredTotal
 * @return {boolean}
 */
var canIWin = function (maxChoosableInteger, desiredTotal) {
	const sum = (maxChoosableInteger * (maxChoosableInteger + 1)) / 2;
	if (desiredTotal <= maxChoosableInteger) return true;
	else if (desiredTotal > sum) return false;
	else if (sum == desiredTotal) return maxChoosableInteger % 2 == 1;

	const memo = new Map();

	const canWin = (used, total) => {
		if (memo.has(used)) return memo.get(used);

		for (let i = 1; i <= maxChoosableInteger; i++) {
			let mask = 1 << i;

			// 如果 i 号数字未被选过
			if ((used & mask) === 0) {
				if (total + i >= desiredTotal || !canWin(used | mask, total + i)) {
					memo.set(used, true);
					return true;
				}
			}
		}

		memo.set(used, false);
		return false;
	};

	return canWin(0, 0);
};

相关题目

题号	标题	题解	标签	难度	力扣
294	翻转游戏 II 🔒		记忆化搜索 数学 动态规划 2+	🟠	🀄️ 🔗
375	猜数字大小 II	[✓]	数学 动态规划 博弈	🟠	🀄️ 🔗
486	预测赢家		递归 数组 数学 2+	🟠	🀄️ 🔗
3222	求出硬币游戏的赢家		数学 博弈 模拟	🟢	🀄️ 🔗
3238	求出胜利玩家的数目		数组 哈希表 计数	🟢	🀄️ 🔗