Climbing stairs

Lesson 7.2 · Easy · Build from last two · 6 min · by Vinay C

We'll cover the following

You can climb 1 or 2 steps at a time. In how many distinct ways can you reach the top of n stairs?

Watch it run

Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.

ground10

·1

·2

·3

·4

·5

·6

·7

·8

·9

·10

·11

·12

·13

·14

·15

dp[i] = number of ways to reach step i. There is 1 way to be on the ground.

1 / 17

Time	Space	Why
`O(n)`	`O(1)`	Only the last two answers are kept.

def climb(n):
    a, b = 1, 1                    # ways(0), ways(1)
    for _ in range(n - 1):
        a, b = b, a + b
    return b

To land on step i you came from i-1 or i-2, so ways(i) = ways(i-1) + ways(i-2). Solve small cases first and write each answer down so you never solve it twice.
Time O(n), space O(1). Only the last two answers are kept.