Dynamic programming solution to “Climbing Stairs”

This is the "Climbing Stairs" problem from leetcode.com:

You are climbing a stair case. It takes $n$ steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given $n$ will be a positive integer.

Example 1:

Input: 2 Output: 2 Explanation: There are two ways to climb to the top.

1. 1 step + 1 step
2. 2 steps

Example 2:

Input: 3 Output: 3 Explanation: There are three ways to climb to the top.

1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

I thought this question is very similar to Fibonacci question. I use dynamic programming,

dp[n] = dp[n - 1] + dp[n - 2]

class Solution:
# @param n, an integer
# @return an integer
def climbStairs(self, n):
dp = [1 for i in range(n+1)]
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]

• I don't know whether the algorithm you use is correct, but you don't need a class, a simple function will do, and instead of a function returning a list, a generator yielding the next value will be a lot more efficient – Maarten Fabré Jan 30 '18 at 9:14
• @MaartenFabré: The problem is from leetcode.com, which always requires an unnecessary Solution class. – Gareth Rees Jan 30 '18 at 11:19
• @NinjaG: When you post these kinds of questions, could you link to the original problem as well as quoting it, please? The original problem helps answer questions like "why is there a Solution class?" – Gareth Rees Jan 30 '18 at 11:20
• Sure. i used the leetcode preparation. leetcode.com/problems/climbing-stairs – NinjaG Jan 31 '18 at 0:09

The code in the post has to compute the $i$th Fibonacci number, $F_i$, for every $i \le n$, in order to compute $F_n$. It's possible to do much better than that, by using the recurrence \eqalign{F_{2n−1} &= F_{n}^2 + F_{n−1}^2 \\ F_{2n} &= (2F_{n−1} + F_{n}) F_{n}} combined with memoization. For example, you could use the @functools.lru_cache decorator, like this:

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci(n):
"""Return the nth Fibonacci number."""
if n <= 1:
return n
elif n % 2:
a = fibonacci(n // 2)
b = fibonacci(n // 2 + 1)
return a * a + b * b
else:
a = fibonacci(n // 2 - 1)
b = fibonacci(n // 2)
return (2 * a + b) * b


this computes the $10^6$th Fibonacci number, which has more than 200,000 decimal digits, in a fraction of a second:

>>> from timeit import timeit
>>> timeit(lambda:fibonacci(10**6), number=1)
0.06556476117111742
>>> len(str(fibonacci(10**6)))
208988


By contrast, the code in the post cannot compute Solution().climbStairs(10 ** 6) without running out of memory.

As far as I understood, Dynamic Programming uses memoization, and calculatig stuff when needed.

Your algorithm calculates all n values all of the time, while the testing code instantiates the class once, and the queries it multiple times. Yu can use that with something like this:

def climb_stairs_gen():
a, b = 1, 2
while True:
yield a
a, b = b, a + b


This is a generator which yields ever-increasing values for longer stairs. You use it in the class like this

from itertools import islice
class Solution:
def __init__(self):
self.values = []
self.generator = climb_stairs_gen()

def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
val = self.values
l = len(val)
if n > l:
val.extend(islice(self.generator, n - l))
return val[n - 1]


It checks whether there is a stairs of lenght n or longer is calculated already. If not, it extends the list with pre-calculated values, then it returns the result for the stairs with length n