A fast Python solution with explanation

  • 0

    The idea is simple. If you can solve the problem for n-1 and n-2, you can solve the problem for n easily. The reason I am using a list to store intermediate result is that the solution for a small n would be used multiple times and you don't want to recompute it.

    class Solution(object):
        def climbStairs(self, n):
            :type n: int
            :rtype: int
            list = [None] * (n+1)
            return self.recur(n, list)
        def recur(self, m, list):
            if m == 1:
                list[1] = 1
                return 1
            if m == 2:
                list[2] = 2
                return 2
            if list[m] is None:
                list[m] = self.recur(m-1, list) + self.recur(m-2, list)
            return list[m]

Log in to reply

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