我能赢吗

难度: Medium

在 "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

Submission

运行时间: 40 ms

内存: 16.7 MB

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:

        @cache
        def dfs(usedNumber, currentTotal):
        
            for i in range(maxChoosableInteger):
                if (usedNumber >> i) & 1 == 0:
                    if currentTotal + i + 1 >= desiredTotal or not dfs(usedNumber | 1 << i, currentTotal + i + 1):
                        return True
            return False
        return (1 + maxChoosableInteger) * maxChoosableInteger // 2 >= desiredTotal and dfs(0, 0)

Explain

此题解采用深度优先搜索（DFS）与记忆化的方法解决问题。首先，通过位操作存储每个数字是否已经被使用，以优化存储和检查。对于每一轮游戏，递归地尝试每一个可用的数字，并将当前选中的数字加到已有的总和上。如果当前玩家选择任意一个数字后直接赢得了游戏（即总和达到或超过所需的总和），或者当前选择使得对手在后续任何操作下都无法赢得游戏，则当前玩家将赢得比赛。如果所有可能的数字都被尝试过后，当前玩家依然无法保证获胜，则返回失败。此外，还有一个预判，如果所有数字之和小于desiredTotal，则直接返回False。

时间复杂度: O(maxChoosableInteger * 2^maxChoosableInteger)

空间复杂度: O(maxChoosableInteger + 2^maxChoosableInteger)

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        from functools import cache

        @cache
        def dfs(usedNumber, currentTotal):
            # 遍历所有可能的选择
            for i in range(maxChoosableInteger):
                # 检查数字i+1是否已被使用
                if (usedNumber >> i) & 1 == 0:
                    # 如果选择当前数字后达到或超过目标，或选择后对手无法赢得比赛
                    if currentTotal + i + 1 >= desiredTotal or not dfs(usedNumber | (1 << i), currentTotal + i + 1):
                        return True
            # 如果所有选择都不能保证赢，则返回False
            return False
        # 预判断，如果所有数字之和还不足以达到desiredTotal，则直接返回False
        return (1 + maxChoosableInteger) * maxChoosableInteger // 2 >= desiredTotal and dfs(0, 0)

Explore

在深度优先搜索中，当`currentTotal + i + 1 >= desiredTotal`条件满足时，意味着当前玩家的选择已经使得累计的总和达到或超过了胜利的条件（desiredTotal）。因此，当前玩家已经直接赢得了游戏。在这种情况下，没有必要继续探索其他可能的数字选择，因为我们已经找到了一种必胜的策略。继续探索其他分支只会浪费计算资源，因为胜利已经通过当前的选择被确定了。

使用位操作来标记已被使用的数字主要基于空间效率和访问速度的优势。位操作允许我们用一个整数的单个位来表示一个数字是否已被选择，这样可以极大地减少内存的使用量，并且通过位运算（如位与、位或和位移）可以快速检查和更新状态。然而，在某些情况下，如数字范围非常大时，位操作可能会受到整数位数的限制，或者当数字范围和序列非常大而且不连续时，使用位数组或布尔数组可能会更直观或易于处理。在这些情况下，位操作的效率和实用性可能不如使用哈希表或数组直接索引。

在记忆化搜索中，`@cache`装饰器的主要作用是存储已经计算过的函数结果，以避免重复计算相同参数的函数调用，从而大幅提高算法的效率。这种方法特别适用于递归函数，其中某些参数组合会被多次调用。如果没有使用记忆化，深度优先搜索中的每个状态可能需要多次重新计算，导致时间复杂度急剧增加。特别是在这种游戏问题中，状态空间可能非常大（取决于`maxChoosableInteger`和`desiredTotal`），没有记忆化的话，算法的时间复杂度将从指数级别的时间复杂度降低到多项式级别，这使得问题在实际应用中变得不可解。