具体题目

问题描述

在 “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），从而取得胜利。
同样地，第一个玩家选择任意其他整数，第二个玩家都会赢。

解题思路

这个问题可以通过记忆化搜索（Memoization）和状态压缩来解决。我们需要考虑所有可能的游戏状态，并判断当前玩家是否可以通过某种选择使得对手处于必输的状态。

关键点

  1. 状态压缩：由于整数不能重复使用，我们可以用一个整数（bitmask）来表示哪些数字已经被使用过。例如，usedNumbers 的第 i 位为 1 表示数字 i+1 已经被使用过。
  2. 记忆化搜索：为了避免重复计算相同的状态，我们可以用一个哈希表（或数组）来存储已经计算过的状态的结果。
  3. 递归判断：对于当前玩家，尝试所有可能的选择（未被使用的数字），如果存在一个选择使得对手处于必输的状态，则当前玩家可以必胜。

算法步骤

  1. 边界条件检查：
    • 如果 maxChoosableInteger >= desiredTotal，先手玩家可以直接选择 desiredTotal 而获胜，返回 true。
    • 如果所有可选整数的和 < desiredTotal，无论如何都无法达到目标，返回 false。
  2. 记忆化搜索：
    • 使用一个数组 memo 来存储状态的结果，memo[state] 表示在状态 state 下当前玩家是否能必胜。
    • 对于当前状态 state，遍历所有未被使用的数字 i：
      • 如果选择 i 后累计和 >= desiredTotal，则当前玩家直接获胜。
      • 否则，递归检查对手是否能必胜。如果对手不能必胜，则当前玩家可以必胜。
  3. 状态压缩：((usedNumbers >> i) & 1) == 0
    • usedNumbers>>i
      usedNumbers 是一个整数（通常是 int 类型），它的二进制形式表示哪些数字已经被使用过（状态压缩）。
      *>> 是usedNumbers右移运算符i，usedNumbers >> i 表示将 usedNumbers 的二进制表示向右移动 i 位。
      作用：把第 i 位移动到最低位（最右边），方便后续检查。
    • usedNumbers>>i & 1
      & 是按位与运算符，& 1 表示只保留最低位的值，其他位全部置 0。
      作用：提取 usedNumbers 的第 i 位的值（0 或 1）。
    • ((usedNumbers >> i) & 1) == 0
      用于判断第i位是否为0。
      作用：检查数字 i+1（因为通常从 1 开始计数）是否未被使用。
      图片
  4. 返回结果：初始状态为所有数字都未被使用（state = 0），调用记忆化搜索函数并返回结果。

代码演示 -解法1

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
31
32
33
34
35
class Solution {
    //一个数来记录这个数是不是已经被使用了
    //dp数组来记录
    //胜利条件 先手必胜 或 后手必败
    //先手必胜-> 取这个数大于目标值了 
    //不用一个值来记录谁先手谁后手 递归是下一次递归必然是另一个人
    HashMap<Integer,Boolean> map=new HashMap<>();
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        //如果所有整数的和小于累加数 直接返回 false
        if(((maxChoosableInteger+1)*maxChoosableInteger)/2<desiredTotal)return false;
        return dfs(maxChoosableInteger,desiredTotal,0,0);
    }
    private boolean dfs(int a,int b,int c,int d){
        if(!map.containsKey(c)){
            boolean res=false;
            for(int i=0;i<a;i++){
                //判断这个数是否已经取过
                if(((c>>i)&1)==0){
                    //满足条件
                    if(i+1+d>=b){
                        res=true;
                        break;
                    }
                    //记录后手 后手输则先手赢
                    if(!dfs(a,b,c|1<<i,d+i+1)){
                        res=true;
                        break;
                    }
                }
            }
            map.put(c,res);
        }
        return map.get(c);
    }
}

代码演示 -解法2

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
31
32
33
class Solution {
    public boolean canIWin(int n, int m) {
        if (m == 0){
            return true;
        }
        if (n * (n + 1) / 2 < m){
            return false;
        }
        int[] dp = new int[1<<(n+1)];
        System.out.println(1 << (n+1));
        System.out.println((1 << (n+1)) - 1);
        return f(n , dp , m , (1 << (n+1)) - 1);
    }
    public boolean f(int n , int[] dp , int rest , int status) {
        if (rest <= 0){
            return false;
        }
        if (dp[status] != 0){
            return dp[status] == 1;
        }
        boolean flag = false;
        for (int i = 1; i <= n; i++){
            int restMid = status ^ (1 << i);
            int represent = status & (1 << i);
            if (represent != 0 && !f(n , dp , rest - i , restMid) ){
                flag = true;
                break;
            }
        }
        dp[status] = flag ? 1 : -1;
        return flag;
    }
}