记忆化搜索+状态压缩leetcode.464

 public static boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        int[] dp=new int[1<<maxChoosableInteger];//某个状态下是否会赢
        //总和小于目标，都会输
        if(desiredTotal>(1+maxChoosableInteger)*maxChoosableInteger/2) return false;
        return dfs(dp,0,maxChoosableInteger,desiredTotal,0);
 
    }
    static boolean dfs(int[] dp,int sum,int maxChoosableInteger,int desiredTotal,int state){
        //如果当前状态已经遍历，返回
        if(dp[state]!=0) {
            if(dp[state]==1)
                return true;
            else return false;
        }
        //寻找未选择的数
            for(int j=0;j<maxChoosableInteger;j++){
                if((state&(1<<j))!=0) continue;
                //如果该数满足条件则赢
                if(sum+j+1>=desiredTotal){
                    dp[state]=1;
                    return true;
                }
                //否则判断是否会导致对方输
                if(!dfs(dp,sum+j+1,maxChoosableInteger,desiredTotal,state|(1<<j))){
                    dp[state]=1;
                    return true;
                }
 
            }
            //无法使自己赢或使对方输，那么自己输
            dp[state]=-1;
            return false;
    }