Medium

题目描述

在"100游戏"中，两名玩家轮流向累计总数中添加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

解题思路

这是一个经典的博弈论问题，需要使用动态规划和状态压缩来解决。

核心思路：

  1. 状态表示：由于数字不能重复使用，我们需要记录哪些数字已被使用。可以用位掩码(bitmask)来表示状态，第i位为1表示数字i+1已被使用。

  2. 博弈分析：这是一个零和博弈，当前玩家想要获胜，必须存在至少一种选择使得对手必败。如果当前玩家的所有选择都会让对手获胜，那么当前玩家必败。

  3. 递归关系：对于当前状态(已使用的数字集合)和剩余目标值，当前玩家能获胜当且仅当：

    • 存在一个可选择的数字，选择后能直接获胜(剩余目标值≤该数字)
    • 或者存在一个可选择的数字，选择后让对手处于必败状态

  4. 记忆化优化：使用哈希表缓存计算结果，避免重复计算相同状态。

  5. 边界情况处理：

    • 如果最大数字≥目标值，第一个玩家直接获胜
    • 如果所有数字总和<目标值，第一个玩家必败

推荐解法：使用位掩码+记忆化递归的动态规划方法，时间复杂度较优且代码简洁。

代码实现

class Solution {
private:
    unordered_map<int, bool> memo;
    
    bool canWin(int used, int remaining, int maxChoosableInteger) {
        if (memo.count(used)) {
            return memo[used];
        }
        
        for (int i = 0; i < maxChoosableInteger; i++) {
            if (!(used & (1 << i))) { // 数字i+1未被使用
                if (remaining <= i + 1 || !canWin(used | (1 << i), remaining - (i + 1), maxChoosableInteger)) {
                    return memo[used] = true;
                }
            }
        }
        
        return memo[used] = false;
    }
    
public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        if (maxChoosableInteger >= desiredTotal) {
            return true;
        }
        
        int sum = maxChoosableInteger * (maxChoosableInteger + 1) / 2;
        if (sum < desiredTotal) {
            return false;
        }
        
        return canWin(0, desiredTotal, maxChoosableInteger);
    }
};

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        if maxChoosableInteger >= desiredTotal:
            return True
        
        total_sum = maxChoosableInteger * (maxChoosableInteger + 1) // 2
        if total_sum < desiredTotal:
            return False
        
        memo = {}
        
        def canWin(used, remaining):
            if used in memo:
                return memo[used]
            
            for i in range(maxChoosableInteger):
                if not (used & (1 << i)):  # 数字i+1未被使用
                    if remaining <= i + 1 or not canWin(used | (1 << i), remaining - (i + 1)):
                        memo[used] = True
                        return True
            
            memo[used] = False
            return False
        
        return canWin(0, desiredTotal)

public class Solution {
    private Dictionary<int, bool> memo = new Dictionary<int, bool>();
    
    private bool CanWin(int used, int remaining, int maxChoosableInteger) {
        if (memo.ContainsKey(used)) {
            return memo[used];
        }
        
        for (int i = 0; i < maxChoosableInteger; i++) {
            if ((used & (1 << i)) == 0) { // 数字i+1未被使用
                if (remaining <= i + 1 || !CanWin(used | (1 << i), remaining - (i + 1), maxChoosableInteger)) {
                    memo[used] = true;
                    return true;
                }
            }
        }
        
        memo[used] = false;
        return false;
    }
    
    public bool CanIWin(int maxChoosableInteger, int desiredTotal) {
        if (maxChoosableInteger >= desiredTotal) {
            return true;
        }
        
        int sum = maxChoosableInteger * (maxChoosableInteger + 1) / 2;
        if (sum < desiredTotal) {
            return false;
        }
        
        return CanWin(0, desiredTotal, maxChoosableInteger);
    }
}

var canIWin = function(maxChoosableInteger, desiredTotal) {
    if (maxChoosableInteger >= desiredTotal) {
        return true;
    }
    
    const sum = maxChoosableInteger * (maxChoosableInteger + 1) / 2;
    if (sum < desiredTotal) {
        return false;
    }
    
    const memo = new Map();
    
    function canWin(used, remaining) {
        if (memo.has(used)) {
            return memo.get(used);
        }
        
        for (let i = 0; i < maxChoosableInteger; i++) {
            if (!(used & (1 << i))) { // 数字i+1未被使用
                if (remaining <= i + 1 || !canWin(used | (1 << i), remaining - (i + 1))) {
                    memo.set(used, true);
                    return true;
                }
            }
        }
        
        memo.set(used, false);
        return false;
    }
    
    return canWin(0, desiredTotal);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(2^n × n)，其中n为maxChoosableInteger。总共有2^n种状态，每种状态需要O(n)时间计算
空间复杂度O(2^n)，用于存储记忆化结果，最多有2^n种不同的状态

相关题目