我能赢吗

你的益达

发布于 2020-08-17 01:44:11

90100

代码可运行

文章被收录于专栏：阿伟的个人博客阿伟的个人博客

运行总次数：0

代码可运行

问题描述：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/can-i-win
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解决方案：

对于博弈类问题，一般做法都是定于fun（）为先手能否获胜。fun计算过程中，枚举出先手方的所有可能，如果存在后手方不能获胜，则此时先手方采取该决策即可获胜，若对于先手方的所有选择后手方均可获胜，则此时先手方不能获胜返回false。

对于该问题，由于题目要求不放回的拿元素，因此需定义一布尔型的visted数组用于存储该元素是否被拿。其dfs实现代码如下：

class Solution {
    int total = 0;
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        this.total = desiredTotal;
        boolean[] visted = new boolean[maxChoosableInteger + 1];
        return step(visted, 0);
    }
    // sum 为当前的和
    public boolean step(boolean[] visted, int sum){
        for(int i = visted.length - 1; i > 0; i--){
            if(visted[i]){
                continue;
            }
            if(sum + i >= total){
                return true;
            }
            visted[i] = true;
            if(!step(visted, sum + i)){
                visted[i] = false;
                return true;
            }
            visted[i] = false;
        }
        return false;

    }
}

上述解法的时间复杂度为O（n!）,其中n为能拿元素的最大值。

由于该过程转移顺序不能确定，因此采用dfs + 记忆集的方式求解。

由于此时的状态为一布尔型的数组，难以存储，因此使用状态压缩的方式，由于题目说道maxChoosableInteger 总是小于20的，因此可以使用一整型变量status，当前位为0表示可用，为1表示不可用。由于是从1开始的，因此i值在status中对应的是i - 1位。由于通过status可以唯一的确定状态，因此不需要加入sum（其实可以通过status得出此时的sum）。

代码如下：

class Solution {
    int total = 0;
    int maxInte = 0;
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if(maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal){
            return false;
        }
        this.total = desiredTotal;
        this.maxInte = maxChoosableInteger;
        int status = 0; // 当前位为0表示未取 1表示已取
        Map<Integer, Boolean> map = new HashMap<>();
        return step(status, map, 0);
    }
    public boolean step(int status, Map<Integer, Boolean> map, int sum){
        if(map.containsKey(status)){
            return map.get(status);
        }
        boolean ans = false;
        for(int i = 0; i < maxInte; i++){
            if((status >> i & 1) == 1){
                continue;
            }

            if(sum + i + 1 >= total){
                ans = true;
                break;
            }
            if(!step(status | (1 << i), map, sum + i + 1)){
                ans = true;
                break;
            }
        }
        map.put(status, ans);
        return ans;   
    }
}