1.题目基本信息

1.1.题目描述

在 "100 game" 这个游戏中，两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，先使得累计整数和 达到或超过 100 的玩家，即为胜者。

如果我们将游戏规则改为 “玩家 不能 重复使用整数” 呢？

例如，两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。

给定两个整数 maxChoosableInteger （整数池中可选择的最大数）和 desiredTotal（累计和），若先出手的玩家能稳赢则返回 true ，否则返回 false 。假设两位玩家游戏时都表现 最佳 。

1.2.题目地址

https://leetcode.cn/problems/can-i-win/description/

2.解题方法

2.1.解题思路

记忆化搜索+状态压缩

2.2.解题步骤

第一步，构建记忆化搜索递归函数。函数返回当前选手在已经选择的数的状态为hasChoose，当前所选数的总和为currentTotal的情况下，是否必胜

第二步，在保证所有待选数字总和大于等于maxChoosableInteger时，调用dfs判断先手是否处于必胜态

3.解题代码

python3代码

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        # 思路：记忆化搜索+状态压缩
        # 第一步，构建记忆化搜索递归函数。函数返回当前选手在已经选择的数的状态为hasChoose，当前所选数的总和为currentTotal的情况下，是否必胜
        @cache
        def dfs(hasChoose:int, currentTotal:int) -> bool:
            for i in range(maxChoosableInteger):
                if (hasChoose >> i) & 1 == 0:
                    # > 选择当前数使当前选手直接胜利或者使对手处于必败态，则当前选手处于必胜态
                    if currentTotal + i + 1 >= desiredTotal or not dfs(hasChoose | (1 << i), currentTotal + i + 1):
                        return True
            return False
        # 第二步，在保证所有待选数字总和大于等于maxChoosableInteger时，调用dfs判断先手是否处于必胜态
        return (maxChoosableInteger + 1) * maxChoosableInteger // 2 >= desiredTotal and dfs(0, 0)

4.执行结果