在 "100 game" 這個游戲中，兩名玩家輪流選擇從 1 到 10 的任意整數(shù)，累計整數(shù)和，先使得累計整數(shù)和達(dá)到 100 的玩家，即為勝者。

如果我們將游戲規(guī)則改為 “玩家不能重復(fù)使用整數(shù)” 呢？

例如，兩個玩家可以輪流從公共整數(shù)池中抽取從 1 到 15 的整數(shù)（不放回），直到累計整數(shù)和 >= 100。

給定一個整數(shù) maxChoosableInteger （整數(shù)池中可選擇的最大數(shù)）和另一個整數(shù) desiredTotal（累計和），判斷先出手的玩家是否能穩(wěn)贏（假設(shè)兩位玩家游戲時都表現(xiàn)最佳）？

你可以假設(shè) maxChoosableInteger 不會大于 20， desiredTotal 不會大于 300。

示例：

輸入：
       maxChoosableInteger = 10
         desiredTotal = 11
輸出：
     false

解釋：
無論第一個玩家選擇哪個整數(shù)，他都會失敗。
第一個玩家可以選擇從 1 到 10 的整數(shù)。
如果第一個玩家選擇 1，那么第二個玩家只能選擇從 2 到 10 的整數(shù)。
第二個玩家可以通過選擇整數(shù) 10（那么累積和為 11 >= desiredTotal），從而取得勝利.
同樣地，第一個玩家選擇任意其他整數(shù)，第二個玩家都會贏。

思路

• 憶化dfs。一開始考慮到A先選，只要有一個選擇的數(shù)返回true就行，B選擇時，需要B之后A的每一次返回true，B才能返回true。這里，B選擇時返回true的含義和A選擇時的true含義是一樣的，true代表A贏。

class Solution {
    public boolean canIWin(int nums, int sum) {
        if(sum==0) return true;
        if((1+nums)*nums/2<sum) return false;
        return dfs(nums,sum,0,new int[1<<20],true);
    }
    boolean dfs(int nums,int sum,int visited,int[] memo,boolean turn){
        if(memo[visited]==1) return true;
        if(memo[visited]==2) return false;
        if(sum<=0){
            if(turn){
                memo[visited]=2;
                return false;
            }
            memo[visited]=1;
            return true;
        }
        for(int i=nums;i>0;i--){
            if(((visited>>(i-1))&1)==1) continue;
            if(turn&&dfs(nums,sum-i,visited|(1<<(i-1)),memo,turn==true?false:true)){//A 一種情況就夠了
                memo[visited]=1;
                return true;
            }
            else if(!turn&&!dfs(nums,sum-i,visited|(1<<(i-1)),memo,turn==true?false:true)){ //B 的每種情況都需要要A贏
                memo[visited]=2;  
                return false;
            }
        }
        if(turn){//A true ,B false
            memo[visited]=2;
        }else{
            memo[visited]=1;
        }
        return !turn;
    }