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.
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