Recursive and dynamic solution in Python


  • 0
    M

    First of all I know there is a more easy way to solve this problem and I did solve it in that mod way at the first time. But I thought what if we treat this as a more computer question, not some math trick. So I decided to redo this problem by recursive and dynamic solution.

    class Solution(object):
        def __init__(self):
            self.result = [None]*10000000
            self.result[1] = True
            self.result[2] = True
            self.result[3] = True
            self.result[4] = False
        def canWinNim(self, n):
            if self.result[n] != None:
                return self.result[n]
            else:
                self.result[n] = not(self.canWinNim(n-1) and self.canWinNim(n-2) and self.canWinNim(n-3))
                return self.result[n]
    

    But this didn't pass the test. Time limit exceeded.
    By the way, is there any way to pass n to init function so I could build a list with a size of n?


Log in to reply
 

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