题目
核心思路
这道题思考了挺长的时间，却始终没有想到解决方案，主要是题目中两位玩家游戏时都表现最佳感觉表示不出来，看了这位大佬的深搜之后豁然开朗。
我之前主要的疑惑是怎么只用一个搜索函数就同时表示出两个玩家的游戏胜负，因为这一轮是我在选数，返回的结果也是我是否能取胜；而下一轮就是对手选数及能否取胜了(其实现在想来，传参是传入一个标识位也是可行的)。在深搜代码中，还是有部分挺值得思考的。
public boolean dfs(int desiredTotal, boolean[] visited){
if(desiredTotal <= 0) return false;
for(int i = 1; i < visited.length; i++){
if(!visited[i]){
visited[i] = true;
boolean tmp = dfs(desiredTotal - i, visited);
visited[i] = false;
if(!tmp) return true;
}
}
return false;
}
代码中的 visited数组 表示的是1-max是否被取过了。而代码的主要部分
if(!visited[i]){
visited[i] = true;
boolean tmp = dfs(desiredTotal - i, visited);
visited[i] = false;
if(!tmp) return true;
}
并不是记录先手的人赢还是后手的人赢，而是返回当前轮游戏中，游戏人(先手的或者后手的)是否能稳赢，这样本轮游戏人(以下以 我 代称)又可以得到下一轮游戏人(以下以 对手 代称)的游戏结果dfs(desiredTotal - i, visited)。这里有两种情况，我 取了 i 这个整数后，要么 对手 可以稳赢，要么 对手 不能稳赢。而其中 对手 不能稳赢也就意味着在他那一轮游戏中出现了 我 可以稳赢的情况。
这里要先回溯在返回，因为 我 并不是特指先手玩家或者后手玩家，我 只是本轮的游戏玩家，而且我 要做出最优的游戏选择，所以 我 就要在所有剩余的取数情况中找到 对手 可以稳输的情况，这样 我 就稳赢了，所以有 if(!tmp) return true; 这样一行代码，对手稳输情况返回true，而 我 的返回值又会交给上一轮的 对手 来考虑策略，这样就可以保证双方都能做出最优的选择，而不会某一轮游戏中一名玩家找到最优解就直接一路return到第一轮游戏。
状压DP
通过上边的深搜，其实不难发现：如果在某次游戏中的某轮游戏中，前面取了[1,2,3]和[2,1,3]对本轮游戏是否稳赢没有影响，因为他们的和都为6，也就是下一轮都要执行 dfs(desiredTotal - 6 - i, visited)，这里的 i 和上边一样用来遍历没取过的数 i。也就是说对于同一个已经取走数的集合([1,2,3]与[2,1,3])，由于剩下的desiredTotal也是相同的，故dfs方法给出的结果也是相同。这样就有了很多重复计算的过程，考虑使用一个memo数组记录也就理所应当了。
因为对于每一个数只有取了或者没取两种状态，而且对于同一个状态，取的顺序并不影响结果。所以可以想到使用状态压缩DP来记录每一种状态。
完整代码
剩下的就是很典型的状压DP计算方法了。
class Solution {
Boolean[] memo = new Boolean[1 << 20];
public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
//先取稳赢
if(maxChoosableInteger >= desiredTotal) return true;
//两人都不能赢
if(((1 + maxChoosableInteger) * maxChoosableInteger / 2) < desiredTotal) return false;
return dfs(maxChoosableInteger, desiredTotal, 0);
}
public boolean dfs(int max, int desiredTotal, int state){
if(memo[state] != null) return memo[state];
for(int i = 0; i < max; i++){
int tmp = 1 << i;
if((tmp & state) == 0){
//我这轮稳赢或者对面下一轮稳输
if(desiredTotal <= i + 1 || !dfs(max, desiredTotal - i - 1, state | tmp)){
memo[state] = true;
return true;
}
}
}
memo[state] = false;
return false;
}
}
对于位运算部分：int tmp = 1 << i; temp & state，通过tmp取到当前状态state是否取到了i + 1这个数，我遍历从零开始主要是移位的时候舒服一点。state | tmp 就是在 state 的基础上取 i + 1 这个数。
总结
虽然方法叫状态压缩DP，其实只是一种枚举的方式，所以主要还是要看数据范围是否能承受O(2^N)的时间复杂度，对于数据范围小于等于30 的问题还是比较好用的，剩下最重要的就是要理解题目的意思了。
如果有写的不正确的地方还请指出，感恩相遇~
