LeetCode Visualizer
How it worksAll visualizations

Step by step · Python

Climbing stairs with dynamic programming, visualized

If you can climb one or two steps at a time, how many different ways are there to reach step n? It is Fibonacci in disguise, and the gentlest introduction to dynamic programming.

How it works
Python
stairs = 8
ways = [0] * (stairs + 1)
ways[0] = 1
ways[1] = 1

for i in range(2, stairs + 1):
    ways[i] = ways[i - 1] + ways[i - 2]

print(ways[stairs])

How climbing stairs works

The last move onto step i came either from step i − 1 or from step i − 2, so ways[i] = ways[i − 1] + ways[i − 2]. With ways[0] and ways[1] both 1, a single loop fills the table from the bottom up, and each answer is computed exactly once.

The example has 8 stairs and returns 34.

What to watch for when it runs

  1. Each new cell is built from the two cells just before it.
  2. Compare with recursive Fibonacci: the same recurrence, but each value is computed once instead of over and over.
  3. Only the last two cells are ever read, which is why this can be done with two variables and O(1) space.

Time and space complexity

Time
O(n)
Space
O(n), or O(1) keeping only two values

One pass, constant work per step — against the exponential number of calls the plain recursive version makes.

Related visualizations

Stuck on your own version?

Paste it into the visualizer and watch your own code run, line by line — bugs included.