LeetCode 464. 我能赢吗

Categories:

题目描述
思路分析
1. 解法一：记忆化搜索 + 位掩码（推荐）
相似题目

题目描述

✅ 464. 我能赢吗

思路分析

解法一：记忆化搜索 + 位掩码（推荐）

核心思路：

用一个整数的二进制位表示每个数字是否已被使用，称为状态掩码（bitmask），最多有 2^maxChoosableInteger 种状态

对每个状态递归判断：当前玩家能否选一个未被使用的数字使总和达到 desiredTotal 或让对手无法赢

用 HashMap 缓存每个状态的结果，避免重复计算

边界条件：若 1+2+…+maxChoosableInteger < desiredTotal，两人都无法赢，返回 false；若 desiredTotal <= 0，当前玩家直接赢

复杂度分析：

时间复杂度：O(2^n × n)，其中 n 为 maxChoosableInteger，共 2^n 个状态，每个状态遍历 n 个选择

空间复杂度：O(2^n)，记忆化缓存的空间

class Solution {

  // 记忆化缓存，键为状态掩码，值为当前先手是否能赢
  private Map<Integer, Boolean> memo = new HashMap<>();

  public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
    // 所有数字之和不足以达到目标，双方都无法赢
    int total = maxChoosableInteger * (maxChoosableInteger + 1) / 2;
    if (total < desiredTotal) {
      return false;
    }

    // 目标为0或负数，先手直接赢
    if (desiredTotal <= 0) {
      return true;
    }

    return canWin(maxChoosableInteger, desiredTotal, 0);
  }

  private boolean canWin(int maxN, int remain, int usedMask) {
    if (memo.containsKey(usedMask)) {
      return memo.get(usedMask);
    }

    for (int i = 1; i <= maxN; i++) {
      // 检查数字 i 是否已被使用
      if ((usedMask & (1 << i)) != 0) {
        continue;
      }

      // 选择数字 i 后达到目标，或对手在新状态下无法赢
      if (remain - i <= 0 || !canWin(maxN, remain - i, usedMask | (1 << i))) {
        memo.put(usedMask, true);
        return true;
      }
    }

    memo.put(usedMask, false);
    return false;
  }
}

func canIWin(maxChoosableInteger int, desiredTotal int) bool {
    // 所有数字之和不足以达到目标
    total := maxChoosableInteger * (maxChoosableInteger + 1) / 2
    if total < desiredTotal {
        return false
    }

    // 目标为0，先手直接赢
    if desiredTotal <= 0 {
        return true
    }

    memo := make(map[int]bool)

    var canWin func(remain, usedMask int) bool
    canWin = func(remain, usedMask int) bool {
        if val, ok := memo[usedMask]; ok {
            return val
        }

        for i := 1; i <= maxChoosableInteger; i++ {
            // 跳过已使用的数字
            if usedMask&(1<<i) != 0 {
                continue
            }

            // 选择 i 后达到目标，或对手在新状态下无法赢
            if remain-i <= 0 || !canWin(remain-i, usedMask|(1<<i)) {
                memo[usedMask] = true
                return true
            }
        }

        memo[usedMask] = false
        return false
    }

    return canWin(desiredTotal, 0)
}

相似题目

题目	难度	考察点
292. Nim 游戏	简单	博弈论、数学
375. 猜数字大小 II	中等	动态规划、博弈
486. 预测赢家	中等	动态规划、博弈
877. 石子游戏	中等	动态规划、博弈
1025. 除数博弈	简单	博弈论、数学
913. 猫和老鼠	困难	博弈、图论、记忆化搜索

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/30376719