# 0464. Can I Win
###### tags: `Leetcode` `Medium` `Backtracking` `Min-Max Strategy`
Link: https://leetcode.com/problems/can-i-win/
## 思路
用dp array记录当下state(state里面包含了已经选过的数字)player是赢还是输
解释递归函数:

if(sum+i>=total){
    dp[state] = 1;
    return true;
}

如果当前state下加一个数可以超过total就说明会赢

if(!dfs(state+(1<<i), sum+i, dp, max, total)){
    dp[state] = 1;
    return true;
}

如果当前state加一个数另外一方必输 说明我方会赢
## Code

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        dp = [0]*(1<<maxChoosableInteger)
        if ((1+maxChoosableInteger)*maxChoosableInteger)//2 < desiredTotal:
            return False

        def dfs(state, currSum):
            # 1 win -1 lose
            if dp[state]!=0: return dp[state]==1
            for i in range(1, maxChoosableInteger+1):
                if ((state>>(i-1))&1)==1: continue
                if currSum+i>=desiredTotal:
                    dp[state] = 1
                    return True
                
                if not dfs(state+(1<<(i-1)), currSum+i):
                    dp[state] = 1
                    return True

            dp[state] = -1
            return False

        return dfs(0, 0)

class Solution {
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        int[] dp = new int[1<<(maxChoosableInteger+1)];
        int totalSum = (maxChoosableInteger+1)*(maxChoosableInteger)/2;
        if(totalSum<desiredTotal) return false;
        return dfs(0, 0, dp, maxChoosableInteger, desiredTotal);
    }
    private boolean dfs(int state, int sum, int[] dp, int max, int total){
        //1 win -1 lose
        if(dp[state]!=0) return dp[state]==1;
        for(int i=1; i<=max; i++){
            if(((state>>i)&1)==1) continue;
            if(sum+i>=total){
                dp[state] = 1;
                return true;
            }
            if(!dfs(state+(1<<i), sum+i, dp, max, total)){
                dp[state] = 1;
                return true;
            }
        }
        dp[state] = -1;
        return false;
    }
}