32 ms solution using memoization beats 99% of Python submissions

  • 0
    def __init__(self):
        self.ways = {}
    def numWays(self, n, k):
        # Each step depends on number of ways from the previous two steps.
        self.ways = {0:0, 1:k, 2:k**2}
        return self.nways(n, k)
    def nways(self, n, k):
        if n not in self.ways:
            self.ways[n] = (k-1)*(self.nways(n-1,k) + self.nways(n-2,k))
        return self.ways[n]

Log in to reply

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