我能赢吗
问题描述：
在 “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;
}
}其时间复杂度降为O（2^N）