题目描述

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

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

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

给定一个整数 maxChoosableInteger （整数池中可选择的最大数）和另一个整数 desiredTotal（累计和），判断先出手的玩家是否能稳赢（假设两位玩家游戏时都表现最佳）？

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

样例

输入：
maxChoosableInteger = 10
desiredTotal = 11

输出：
false

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

算法1

(记忆化搜索) $O(2^n)$

由于是不放回的抽取，即每个数只能选一次，并且最大可选的数不会超过20，所以我们可以用一个int型的数来表示整数池中的数是否被选过，这里第0位表示整数1是否被选过，第1位表示整数2是否被选过，以此类推。

之后我们可以用dfs(u, t)来搜索在具有整数池u同时desiredTotal只剩下t的情况下当前玩家是否可以获胜。显然当t <= 0时即对手已经达到了desiredTotal时，当前玩家就输了。否则我们枚举整数池中可选的每个数，如果选择当前数后剩下的局面对手无论怎么选都会输，那么我们就找到了一种必胜的情况。

这里游戏的局面是被整数池u的使用状况完全决定的，因为u中使用了多少个数相应的desiredTotal就会减去多少个数，即t是依赖于u的。并且在dfs的过程中有很多游戏局面会被重复计算，比如玩家1先选了1然后玩家2选了2和玩家1选2然后玩家2选1所剩下的整数池是一样的，即1和2被选过。所以我们可以开一个数组来缓存所有已经被计算过的游戏局面，初始时数组为-1来表示所有局面还未被计算过，注意这里不能初始化成0，不然就成了所有局面初始都是输的情况了。

还有这里要特判开始时desiredTotal为0的情况，因为开始时为0说明可以直接获胜，而在DFS搜索的时候为0表示当前已输。同时还有整数池的和小于desiredTotal的情况，此时应该直接判负，而当n为奇数时DFS会返回true形成矛盾。

时间复杂度

设maxChoosableInteger为n，则共有 $2^n$ 中不同的局面，计算这些局面至少需要 $O(2^n)$ 的复杂度。

C++ 代码

class Solution {
public:
    int m;
    vector<int> f;
    bool canIWin(int _m, int t) {
        m = _m;
        if (m * (m + 1) < t * 2) return false;
        if (!t) return true;
        f.resize(1 << (m + 1), -1);

        return dfs(0, t);
    }

    bool dfs(int u, int t) {
        if (f[u] != -1) return f[u];
        if (t <= 0) return f[u] = false;

        for (int i = 1; i <= m; i ++ ) {
            if (!(u & 1 << i)) {
                if (!dfs(u + (1 << i), t - i)) {
                    return f[u] = true;
                }
            }
        }
        return f[u] = false;
    }
};

算法2

(动态规划) $O(2^n)$

由于使用了记忆化搜索，那么本题也可以用动态规划来做。设dp[i]表示在游戏局面为i的情况下当前玩家是否能获胜，则答案为dp[0]。

在计算dp[i]时我们先判断当前整数池中用过的数的和是否已经大于等于desiredTotal，若是则说明对手已经获胜，我们直接判负。否则我们枚举所有还没用过的数，看使用当前数后是否会造成对手必败，即dp[i + (1 << k)]是否为false，若是则可以判断当前是一个必胜局面。

时间复杂度

与记忆化搜索一样，不过由于记忆化搜索找到一个必胜局面后就会返回，因此在实践中通常不会达到 $O(2^n)$ 的复杂度，而动态规划则是一定会循环 $O(2^n)$ 次。

C++ 代码

class Solution {
public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        if (!desiredTotal) return true;
        int n = maxChoosableInteger;
        if (n * (n + 1) / 2 < desiredTotal) return false;
        vector<bool> dp(1 << n, false);

        for (int i = (1 << n) - 1; i >= 0; i -- ) {
            int sum = 0;
            for (int k = 0; k < n; k ++ )
                if (i >> k & 1) sum += k + 1;
            if (sum < desiredTotal) {
                for (int k = 0; k < n; k ++ )
                    if (!(i >> k & 1)) {
                        dp[i] = dp[i] || !dp[i + (1 << k)];
                    }
            }
        }
        return dp[0];
    }
};