minmax with bit-wise memorization


  • 1
    S

    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
            mask=1
            while mask<=nums:
                if nums&mask>0 and not self.minmax(nums^mask,target-i):
                    self.dp[nums]=True
                    break
                mask<<=1
                i+=1
            return self.dp[nums]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.