# minmax with bit-wise memorization

• it's a common minmax problem in game theory, and the key point is to utilize memorization to reduce the repeated computation.
The status is the numbers which are not selected and the `desiredTotal` util now. since the `desiredTotal` could be computed by the available numbers for each game, the numbers is enough to represent the status. And to traverse the available numbers and record the status efficiently, we can use bit-wise mask to record the the available numbers, instead of array or set. The python solution is 659 ms in my submission.

``````class Solution(object):
def canIWin(self, maxChoosableInteger, desiredTotal):
"""
:type maxChoosableInteger: int
:type desiredTotal: int
:rtype: bool
"""
if desiredTotal<=0:
return True
if maxChoosableInteger*(maxChoosableInteger+1)/2<desiredTotal:
return False
self.dp={}
return self.minmax((1<<maxChoosableInteger)-1,desiredTotal)

def minmax(self,nums,target):
if target<=0:
return False
if nums in self.dp:
return self.dp[nums]
else:
self.dp[nums]=False
i=1