LeetCode 464. 我能赢吗

约 5 分钟
文章信息 6 个分类 6 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 阿里
标签
动态规划 数学 位运算 记忆化 位掩码 博弈

题目描述

✅ 464. 我能赢吗

image-20260929100717002

image-20260929100717099

题意分析

双方轮流从 1 到 maxChoosableInteger 的公共整数池中选一个尚未使用的数，加到共同的累计和中。谁先使累计和达到或超过 desiredTotal，谁就获胜。两人都采取最优策略，判断先手能否保证获胜。

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

核心思路

[!blue]

最大可选数 M 不超过 20，可以用位掩码 used 表示已经选过的数字：第 pick - 1 位为 1，就表示 pick 已用。已用集合确定了累计和，也就确定了剩余目标 remaining 和所有可选数，因此即使到达同一集合的选取顺序不同，之后的局面也相同。

定义 canWin(used, remaining) 表示当前行动玩家能否必胜。枚举一个未使用的 pick：若 pick >= remaining，本轮直接获胜；否则进入对手的回合，只要 canWin(used | bit, remaining - pick) 为 false，当前玩家就能靠这个选择保证获胜。若所有选择都会让对手必胜，当前局面才是必败。

搜索结果只需按 used 缓存，remaining 作为参数只是避免重复计算集合的和。缓存用 0、1、-1 分别表示未计算、必胜、必败，不能用默认 false 同时表示未知和失败。每次选择都会增加一个已用数字，递归最多深入 M 层，不会成环。

搜索前先处理两个边界：目标不大于 0 时已满足条件；所有可选数的总和仍小于目标时，任何人都无法达到目标，先手不能保证获胜。后一种情况必须先排除，剩下的对局最迟会在取完全部数字时分出胜负。

解题步骤

  1. desiredTotal <= 0 时返回 true；1 + 2 + ... + M < desiredTotal 时返回 false。
  2. 创建长度为 1 << M 的三态缓存，从 used = 0、remaining = desiredTotal 开始搜索。
  3. 若当前掩码已有结果，直接返回；否则枚举所有尚未使用的数。
  4. 找到能直接达标或让对手必败的选择，就缓存 1 并返回 true。
  5. 所有选择都失败时，缓存 -1 并返回 false。

代码实现

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(M2^M)$，M 为最大可选数，每个掩码至多枚举 M 个选择。
  • 空间复杂度：$O(2^M)$，记忆数组占主导，递归栈至多 M 层。

关键点总结

[!green]

  • 存在一个让对手失败的选择即可获胜。
  • 掩码决定剩余目标，无需把两个量都作为缓存键。
  • 每次公开调用重新建立缓存，目标不同不能混用。

易错点总结

[!yellow]

  • 递归结果不取反：把对手必胜当成自己必胜。
  • 只按剩余目标缓存：同样剩余目标可能拥有不同可选集合。
  • 默认 false 就当已计算必败：混淆未知状态。
  • 达标不包含相等：漏掉累计和恰好达到目标的获胜方式。

相似题目

题目 难度 关联与区别
486. 预测赢家 中等 同样在双方最优策略下判胜负，原题可选区间两端，本题可选任意未使用整数，需要访问集合状态。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/30376719
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！