464. 我能赢吗#

1
在 "100 game" 这个游戏中，两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，
2

3
先使得累计整数和达到或超过 100 的玩家，即为胜者。
4

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

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

9
给定一个整数 maxChoosableInteger 和另一个整数 desiredTotal，判断先出手的玩家是否能稳赢？
10

11
你可以假设 maxChoosableInteger 不会大于 20， desiredTotal 不会大于 300。
12

13
示例：
14

15
输入：
16
maxChoosableInteger = 10
17
desiredTotal = 11
18

19
输出：
20
false
21

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

1
class Solution {
2
public:
3
    bool canIWin(int stable, int desired) {
4
        if (stable >= desired) return true;
5

6
        if (stable * (stable + 1) / 2 < desired) return false;
7

8
        unordered_map<int, bool> up;
9
        return dfs(stable, desired, 0, up);
10
    }
11

12
    bool dfs(int n, int sum, int k, unordered_map<int, bool>& up) {
13
        if (up.count(k)) return up[k];
14

15
        for (int i = 0; i < n; ++i) {
16
            int cur = (1 << i);
17
            if ((cur & k) == 0)
18
            {//这个值没有使用过
19
                if (sum <= i + 1 || !dfs(n, sum - (i + 1), cur | k, up))
20
                {
21
                    up[k] = true;
22
                    return true;
23
                }
24
            }
25
        }
26
        up[k] = false;
27
        return false;
28
    }
29
};