我能赢吗

---

image.png

特例一：如果最大能选择的数字maxChoosableInteger比期望的总数desiredTotal要大，先手稳赢，返回True

特例二：如果能选择的所有数字总和比期望的总数desiredTotal要小，一定到达不了desiredTotal，先手稳输，返回False

if(maxChoosableInteger>desiredTotal){
  return True
}
if((1+maxChoosableInteger)*maxChoosableInteger/2 < desiredTotal){
  return False
}

用二进制位来标记某个数是否已被选择，比如01表示1已被选择，10表示2已被选择，11表示1和2都被选择，100表示3被选择，以此类推，1 << (n - 1)1<<(n−1) 表示n已被选择

• 先1，2再3，4与先4，3后1，2是一样的效果，所以需要基于state记忆性去重而不是罗列所有的情况，因为可以他们的效果一样可以合并。

情况1我抽牌：只要我出某一张牌，对方遍历了所有方法helper(statenow|choosedpoint,value,desired)都是输那我就赢了。
情况2对手抽牌：不论对方抽哪张牌都是死。

class Solution:
    # return 0 我稳输 1 我稳赢
    def helper(self,dp,state,value,maxChoosableInteger,desiredTotal,terms):
        if(dp[state]!=10):
            return dp[state]
        if terms%2==1:
            # 我执手,对手有一种情况全输即可，helper有一个返回1我就能赢
            res=0
            for i in range(0,maxChoosableInteger):
                if res==1:
                    break
                if state&(1<<i)==0:
                    if(value+i+1>=desiredTotal):
                        # now
                        res=1
                        break
                    else:
                        res|=self.helper(dp,state+(1<<i),value+i+1,maxChoosableInteger,desiredTotal,terms+1)
            if(res==1):
                dp[state]=1
                return 1
            else:
                dp[state]=0
                return 0
        else:
            # 对手执手,我helper得全赢helper全返回1我才能赢
            res=1
            for i in range(0,maxChoosableInteger):
                if res==0:
                    break
                if state&(1<<i)==0:
                    if(value+i+1>=desiredTotal):
                        res=0
                        break
                    else:
                        res&=self.helper(dp,state+(1<<i),value+i+1,maxChoosableInteger,desiredTotal,terms+1)
            if(res==1):
                dp[state]=1
                return 1
            else:
                dp[state]=0
                return 0

    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        # 特殊情况两种
        if desiredTotal<=maxChoosableInteger:
            return True
        if((1+maxChoosableInteger)*maxChoosableInteger/2 < desiredTotal):
            return False
        dp=[10 for i in range(1<<maxChoosableInteger)]
        return self.helper(dp,0,0,maxChoosableInteger,desiredTotal,1)==1