我能赢吗

LC464. 我能赢吗

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

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

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

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

输入：maxChoosableInteger = 10, desiredTotal = 11
输出：false
解释：
无论第一个玩家选择哪个整数，他都会失败。
第一个玩家可以选择从 1 到 10 的整数。
如果第一个玩家选择 1，那么第二个玩家只能选择从 2 到 10 的整数。
第二个玩家可以通过选择整数 10（那么累积和为 11 >= desiredTotal），从而取得胜利.
同样地，第一个玩家选择任意其他整数，第二个玩家都会赢。

思路：记忆化递归

先将 1 ~ maxChoosableInteger 累加起来，判断能否到达 desiredTotal，如不能，直接返回 false
记忆化递归，需要四个参数：可选择的最大数 maxChoosableInteger；已选择的数（用二进制表示）usedNumbers；目标累计和 desiredTotal，当前累计和 currentTotal
通过 dfs，先遍历 1~maxChoosableInteger，选出还没用过的数，然后判断加上这个数是否大于 desiredTotal，若大于，直接为 true
若不大于，则判断我用上这个数后，对反取数时是否返回 false，如果是，我则为 true
通过 map 来存储已使用过的数字中，我是否能赢的结果，减少递归次数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


class Solution {
public:
    unordered_map<int, bool> map;
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        if ((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal) {
            return false;
        }
        return dfs(maxChoosableInteger, 0, desiredTotal, 0);
    }

    bool dfs(int maxChoosableInteger, int usedNumbers, int desiredTotal, int currentTotal) {
        if (map.find(usedNumbers) == map.end()) {
            bool res = false;
            for (int i = 0; i < maxChoosableInteger; i++) {
                if ((usedNumbers >> i & 1) == 0) {
                    if (i + 1 + currentTotal >= desiredTotal) {
                        res = true;
                        break;
                    }
                    if (!dfs(maxChoosableInteger, usedNumbers | (1 << i), desiredTotal, currentTotal + i + 1)) {
                        res = true;
                        break;
                    }
                }
            }
            map[usedNumbers] = res;
        }
        return map[usedNumbers];
    }
};

LC464. 我能赢吗

相关文章：