Python solution with detailed explanation


  • 1
    G

    Solution

    Can I Win https://leetcode.com/problems/can-i-win/

    Top Down DFS with Memoization: Time: O(N * 2^N). Space: O(2^N)

    • We create an array allowed which has all the integers from 1 to maxChoosableInteger.
    • We test if the input is valid or not i.e. sum(allowed) >= desiredTotal.
    • How do we define the state of the game? This answer determines how we will do memoization as well. Clearly list of current allowed numbers are needed to define the state. It might also look that so_far is also required to define the state. However, given all allowed values and the current set of allowed values, so_far is really the difference of the sum of the two. Therefore only allowed values uniquely determine the state.
    • How many allowed values sets are possible? The length of the allowed value set can range 1 to maxChoosableInteger(N). So the answer is (N,1) + (N,2) + ..(N,N) where (N,K) means choose K from N. This is equal to 2^N.
    • Now at my turn, if the max(allowed) + so_far >= target, then I will win. Otherwise, I choose from the allowed values one by one and recursively call for the other player. If with any choice the opponent fails for sure, then also I can win for sure from this state.
    • What is the time complexity? For a brute force solution, the game tree has 10 choices at first level, each of these choices has 9 choices at second level, and so on. So the complexity is N!. But with memoization, we only compute 2^N sub-problems, and in each problem we do O(N) work. So total time complexity is O(N2^N).
    class Solution(object):
        def helper(self, allowed, target, so_far, cache):
            if len(allowed) == 0:
                return False
            state = tuple(allowed)
            if state in cache:
                return cache[state]
            else:
                cache[state] = False
                if max(allowed) + so_far >= target:
                    cache[state] = True
                else:
                    for x in allowed:
                        new_allowed = [y for y in allowed if x!=y]
                        if self.helper(new_allowed, target, so_far+x, cache) ==  False:
                            cache[state] = True
                            break
                return cache[state]
        
        def canIWin(self, maxChoosableInteger, desiredTotal):
            """
            :type maxChoosableInteger: int
            :type desiredTotal: int
            :rtype: bool
            """
            allowed = [x for x in range(1, maxChoosableInteger+1)]
            if sum(allowed) < desiredTotal:
                return False
            return self.helper(allowed, desiredTotal, 0, {})
    

  • 0
    R

    This is the best explanation so far and most readable code. Thanks!


  • 0

    There is another initial case to check for early termination when

    • sum of allowed == desiredTotal.

Log in to reply
 

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