LC-464.我能赢吗

题目描述

leetcode 中等题

两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，先使得累计整数和 达到或超过  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

递归 (TLE)

最无脑的做法是直接递归, 用一个 List 来模拟选数的情况，每次选走一个数时 remove 掉对应元素即可，但同时因为要找到最优决策，所以不能改变原集合，只能改变拷贝的 List（如果直接对原集合 remove ，递归结束后不好还原，重新 add 会添加到集合末尾，那整个 for 循环遍历集合就不正确了）

class Solution {
    public boolean canIWin(int n, int dest) {
        return dfs(IntStream.rangeClosed(1, n).boxed().collect(Collectors.toList()), dest);
    }

    private boolean dfs(List<Integer> list, int dest){
        int n = list.size();
        boolean ans = false;
        for(int i = 0; i < n; i++){
            int item = list.get(i);
            if(item >= dest){
                return true;
            }
            List<Integer> copy = new ArrayList<>(list);
            copy.remove(i);
            boolean flag = dfs(copy, dest - item);
            if(flag == false){
                return true;
            }
        }
        return ans;
    }
}

状态压缩 + 记忆化搜索

上面方案有问题的地方在于直接使用了 List 模拟选数过程，而整个递归过程是存在很多重复计算的，使用 List 无法进行记忆化搜索。

所以容易发现从一开始使用 List 就是一个 错误的思路 。

由于 n 数据范围为 20，且每个数只能被选择一次，所以我们可以 用一个 int (32位) 来表示选数的情况（状态压缩），对应二进制为 1 代表已被选择，否则代表未被选择。这种方案的好处在于很容易就能实现 记忆化搜索，不管是用 int[1 << 20] 又或者是 Map<Integer, Integer> 。

整体实现的逻辑还是和上面的版本一样的：

class Solution {
    int[] cache = new int[1 << 20]; // int 的第 n 位为 1 代表 n - 1 被选择
    int n;

    public boolean canIWin(int n, int dest) {
        if (n * (n + 1) / 2 < dest) return false; // 依题意平手算先出手的玩家输
        this.n = n;
        return dfs(0, dest) == 1;
    }

    private int dfs(int state, int dest){
        if(cache[state] != 0){
            return cache[state];
        }
        for(int i = 1; i <= n; i++){
            if(((state >> (i - 1)) & 1) == 1){
                // 玩家不能重复使用整数
                continue;
            }
            if(i >= dest){
                return cache[state] = 1;
            }
            if(dfs((state | (1 << (i - 1))), dest - i) == -1){
                return cache[state] = 1;
            }
        }
        return cache[state] = -1;
    }

}