LC.P464[我能赢吗]

题目描述

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

方法一：记忆化搜索+状态压缩

为什么可以想到使用int型整数标记状态？

  1. 范围可以，题目说 1 <= maxChoosableInteger <= 20，也就是不超过int的32位
  2. 公共整数池中的所有数字是连续的，即从1到maxChoosableInteger，不重复
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
class Solution {
    Map<Integer, Boolean> cache = new HashMap<>();

    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if (maxChoosableInteger >= desiredTotal) return true;
        if ((maxChoosableInteger + 1) * maxChoosableInteger / 2 < desiredTotal) return false;
        return dfs(0, 0, maxChoosableInteger, desiredTotal);
    }

    private boolean dfs(int state, int sum, int maxChoosableInteger, int desiredTotal) {
        if (cache.containsKey(state)) return cache.get(state);
        for (int x = 1; x <= maxChoosableInteger; ++x) {
            if (((1 << x) & state) == 0) { // 若x未被使用
                if (sum + x >= desiredTotal) {
                    cache.put(state, true);
                    return true;
                }
                // 当前玩家选择x后，判断对方一定会输吗?若对方一定输，则当前玩家一定赢
                if (!dfs((1 << x) | state, sum + x, maxChoosableInteger, desiredTotal)) {
                    cache.put(state, true);
                    return true;
                }
            }
        }
        cache.put(state, false);
        return false;
    }
}
  • 时间复杂度：$O(2^n\times n)$
  • 空间复杂度：$O(2^n)$