Iterative Python code using recursive idea

  • 1

    This problem is a typical recursive question. We should think backward.

    Say we are standing on the nth step, we have two ways to get here --> through one step or two step, so we just need to add those two ways.

    There are a_(n-1) for the the front, and a_(n-2) for the latter. Thus a_n = a_(n-1) + a_(n-2)

    Next we go from 3 to generate the result using this formula (my recursive solution exceeded the time limit).

    def climbStairs(self, n):
        if n < 3:
            return n
        a, b, result = 1, 2, 0
        for i in range(3, n+1):
            result = a + b
            a, b = b, result
        return result

Log in to reply

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