LeetCode 464. 我能赢吗

2025-02-15 HGNULB 约 6 分钟

文章信息 6 个分类 6 个标签

分类

题目描述

✅ 464. 我能赢吗

题意分析

题目目标：两名玩家轮流从 1 到 maxChoosableInteger 这些整数中挑选，每个数字全局只能被选一次，被选中的数字累加进一个公共的总和，谁先让总和达到或超过 desiredTotal 谁就获胜。问先手在双方都采取最优策略的前提下能否必胜。
核心约束：「双方都最优」这五个字决定了这是一道博弈搜索题而非贪心题——不能假设对手会犯错，必须假设对手每一步都走对自己最有利的选择。数字不可重复使用，且每个数字只有「用过」和「没用过」两种状态，这提示我们可以用一个整数的二进制位来完整描述局面。最关键的约束是 maxChoosableInteger 不超过 20，$2^{20}$ 约一百万，恰好落在可以枚举全部状态的量级——这个数字几乎是在明示状态压缩。
边界处理：desiredTotal 可能小于等于 0，此时先手还没开始就已经达标，直接判胜；所有数字加起来可能都够不到 desiredTotal，此时双方都无法取胜，按题意先手不能获胜，返回 false；单个数字可能一步就超过目标，这种情况要能立刻判胜而不必继续递归；掩码用第 1 位到第 maxChoosableInteger 位表示数字 1 到 maxChoosableInteger 时，第 0 位是空置的，移位写法要保持一致。

解法：记忆化搜索 + 位掩码

核心思路

不同的选择顺序可能得到同一个“已用数字集合”，而集合又唯一决定当前累计和与剩余可选数字。因此用位掩码表示集合：第 pick-1 位为 1 表示数字 pick 已使用。

定义 canWin(used, remaining)：在已用集合为 used、距离目标还差 remaining 时，轮到当前玩家能否必胜。记忆化只需使用 used 作键，因为 remaining = desiredTotal - 已用数字之和，由掩码唯一确定。

当前玩家枚举每个未使用数字：若 pick >= remaining，本轮直接获胜；否则若递归后的对手状态必败，当前玩家也能通过这一选择获胜。存在一个必败后继就是必胜态；所有合法选择都让对手必胜，当前状态才是必败态。

这个递推正确地实现了双方最优：必胜态保存至少一种获胜策略，必败态则证明对手能应对当前玩家的所有选择。记忆化让每个使用集合只计算一次。

解题步骤

若 desiredTotal <= 0，先手已经满足目标，返回 true。

若 1..maxChoosableInteger 的总和仍小于目标，返回 false。

建立大小为 2^maxChoosableInteger 的三态记忆数组：未知、必胜、必败。

在递归中枚举未使用数字；能立即达标或能把必败态交给对手时，记录必胜。

所有数字都不能带来胜利时，记录必败。

maxChoosableInteger = 10, desiredTotal = 11 时，先手选任意 pick，后手都能选择 11-pick 立即获胜，所以先手必败。目标为 1 时，先手选择 1 即可获胜。

代码实现

class Solution {
    private int maxChoosable;
    private byte[] memo;

    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if (desiredTotal <= 0) {
            return true;
        }
        int total = maxChoosableInteger * (maxChoosableInteger + 1) / 2;
        if (total < desiredTotal) {
            return false;
        }
        maxChoosable = maxChoosableInteger;
        memo = new byte[1 << maxChoosableInteger];
        return canWin(0, desiredTotal);
    }

    private boolean canWin(int used, int remaining) {
        if (memo[used] != 0) {
            return memo[used] == 1;
        }
        for (int pick = 1; pick <= maxChoosable; pick++) {
            int bit = 1 << (pick - 1);
            if ((used & bit) != 0) {
                continue;
            }
            if (pick >= remaining || !canWin(used | bit, remaining - pick)) {
                memo[used] = 1;
                return true;
            }
        }
        memo[used] = -1;
        return false;
    }
}

func canIWin(maxChoosableInteger int, desiredTotal int) bool {
	if desiredTotal <= 0 {
		return true
	}
	total := maxChoosableInteger * (maxChoosableInteger + 1) / 2
	if total < desiredTotal {
		return false
	}

	memo := make([]int8, 1<<maxChoosableInteger)
	var canWin func(int, int) bool
	canWin = func(used, remaining int) bool {
		if memo[used] != 0 {
			return memo[used] == 1
		}
		for pick := 1; pick <= maxChoosableInteger; pick++ {
			bit := 1 << (pick - 1)
			if used&bit != 0 {
				continue
			}
			if pick >= remaining || !canWin(used|bit, remaining-pick) {
				memo[used] = 1
				return true
			}
		}
		memo[used] = -1
		return false
	}
	return canWin(0, desiredTotal)
}

复杂度分析

时间复杂度：$O(n2^n)$。至多计算 $2^n$ 个掩码，每个状态枚举 n 个数字。

空间复杂度：$O(2^n)$ 用于记忆数组，递归栈深度为 $O(n)$。

关键点总结

当前必胜当且仅当存在一个选择，使对手进入必败态。

数字只分已用和未用，且最多 20 个，适合用位掩码表示集合。

剩余目标由已用集合唯一决定，所以记忆化键只需掩码。

三态缓存必须区分未知、必胜、必败，普通布尔数组无法表示未知。

总和不足的无解情况应在搜索前直接排除。

易错点总结

忘记对递归结果取反，会把“对手必胜”误当成当前玩家必胜。

达标条件必须包含相等；选择后累计和恰好达到目标也立即获胜。

只用 remaining 作缓存键会混淆可选集合不同的局面。

位号约定必须统一；数字 pick 对应第 pick-1 位。

用布尔数组且默认 false 会把“尚未计算”误当成必败。

多次调用方法时必须重新初始化记忆数组，避免不同目标间缓存串用。

相似题目

题目	难度	考察点
486. 预测赢家	中等	同为轮流取数的博弈，但取法受限于两端，状态用区间而非集合表示
877. 石子游戏	中等	区间博弈的特例，可用记忆化搜索求解，也存在先手必胜的数学结论
292. Nim 游戏	简单	同样是必胜态判定，但可从小规模归纳出模 4 的闭式结论，无需搜索
698. 划分为k个相等的子集	中等	同样用掩码表示已用元素集合做记忆化搜索，目标从博弈换成可行性划分
847. 访问所有节点的最短路径	困难	状态压缩的另一典型形态，掩码记录已访问节点并配合广度优先搜索求最短步数