Climbing Stairs

The problem

A staircase has n stairs, given as stairs. Each move climbs either 1 stair or 2 stairs. Return how many different sequences of moves take you from the bottom to the top.

Example 1

Input: stairs = 5

Output: 8

For example 1+1+1+1+1, 2+2+1, 2+1+2, 1+2+2 and 1+1+1+2. There are 8 sequences in all.

stairs

012345

Example 2

Input: stairs = 1

Output: 1

A single 1-stair move.

Example 3

Input: stairs = 4

Output: 5

1+1+1+1, 1+1+2, 1+2+1, 2+1+1 and 2+2.

Constraints

• 1 ≤ n ≤ 45

Clarifying questions

Does the order of moves matter?

Yes. 1+2 and 2+1 are two different ways.

Can a move overshoot the top?

No. The moves must end exactly on stair n.

How big can the answer get?

For n = 45 it is 1,836,311,903, which still fits in a 32-bit integer.

Spot the pattern

Think about the last move. It was either 1 stair, from stair n − 1, or 2 stairs, from stair n − 2. So the ways to reach n are the ways to reach n − 1 plus the ways to reach n − 2. The answer is built from answers to smaller versions of the same question, and those smaller answers repeat. That is dynamic programming.

Solutions

Plain recursionO(2ⁿ)Recursion with a memoO(n)Two numbersO(n)

Show all

Plain recursion O(2ⁿ)

The idea

Write the rule straight down as a function: ways(stair) = ways(stair - 1) + ways(stair - 2). The rule needs a place to stop. There is 1 way to climb 1 stair, and 1 way to climb 0 stairs: do nothing. So ways(0) and ways(1) both return 1.

Why it is correct: every sequence of moves ends with a 1 or a 2, never both. So the sequences that reach n split into two groups with no overlap, and the two calls count each group.

Walkthrough

calls so far

0

1. def ways(stair):
2. if stair <= 1: return 1
3. return ways(stair - 1) + ways(stair - 2)

To reach stair 5, the last move was 1 step from stair 4 or 2 steps from stair 3. So ways(5) = ways(4) + ways(3). The picture is every call this makes. w(k) stands for ways(k).

← BackStep →Play1 / 14

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Plain recursion: the last move was 1 step or 2 steps, so add the ways to
    // reach the two stairs below. The same stairs get solved again and again.
    public int climbStairs(int stairs) {
        // 0 stairs or 1 stair: exactly one way.
        if (stairs <= 1) return 1;
        return climbStairs(stairs - 1) + climbStairs(stairs - 2);
    }
}

Big O

Time O(2ⁿ)Space O(n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The work repeats through recursion, so we count the calls of ways. Each call does one check and one addition, a fixed job, so each call counts as 1 step.

   1. def ways(stair):
   2. if stair <= 1: return 1
   3. return ways(stair - 1) + ways(stair - 2)

2. 2 Count the runs on Example 1

   The table counts how many times each stair was asked for. Small stairs are asked for again and again: ways(1) five times.

   1 + 1 + 2 + 3 + 5 + 3 = 15 calls.

   call	ways(5)	ways(4)	ways(3)	ways(2)	ways(1)	ways(0)
   times called	1	1	2	3	5	3

   total

   1 + 1 + 2 + 3 + 5 + 3 = 15 calls

3. 3 Write the count for any n

   Each call makes at most 2 more calls, and each step down the tree lowers n by at least 1, so the tree is at most n levels deep below the first call. Level d holds at most 2ᵈ calls:

   1 + 2 + 4 + … + 2ⁿ = 2ⁿ⁺¹ − 1 calls

   Check it with Example 1: 2⁶ − 1 = 63 at most. The real run made 15, because the n − 2 side of the tree is shorter. The true growth is about 1.6ⁿ, still exponential.

4. 4 Keep only the part that grows fastest

   Drop the 2 and the − 1. What is left is 2ⁿ. For n = 45 that is over a billion calls.

   So the time is O(2ⁿ).

5. S Space: count the extra memory the same way

   Only one path of the tree is on the call stack at a time, and a path is at most n + 1 calls long. So the space is O(n).

   call stack (up to n deep)

Recursion with a memo O(n)

The idea

The plain recursion is slow only because it solves the same stair many times. So keep a memo, a map from stair to answer. The first time ways(stair) is worked out, save it. Every later call for that stair returns the saved answer at once.

Why it is correct: ways(stair) always returns the same number, so reusing a saved answer changes nothing but the speed.

Walkthrough

memo

10112345

1. memo = {}
2. def ways(stair):
3. if stair <= 1: return 1
4. if stair in memo: return memo[stair]
5. memo[stair] = ways(stair - 1) + ways(stair - 2)
6. return memo[stair]

Same recursion, plus a memo: once ways(k) is known, write it down. Stairs 0 and 1 are base cases, 1 each. These are all the calls ways(5) makes now.

← BackStep →Play1 / 11

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    private final java.util.Map<Integer, Integer> memo = new java.util.HashMap<>();

    // Recursion with a memo: the same idea, but save each stair's answer the first
    // time it is found. Each stair is solved once, so the work is O(n).
    public int climbStairs(int stairs) {
        if (stairs <= 1) return 1;
        // Solved before: reuse it instead of recursing again.
        if (memo.containsKey(stairs)) return memo.get(stairs);
        int result = climbStairs(stairs - 1) + climbStairs(stairs - 2);
        memo.put(stairs, result);
        return result;
    }
}

Big O

Time O(n)Space O(n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Again we count the calls of ways. A call is a base case, a memo lookup, or one addition that is then saved. Each is a fixed job, so 1 step.

   1. memo = {}
   2. def ways(stair):
   3. if stair <= 1: return 1
   4. if stair in memo: return memo[stair]
   5. memo[stair] = ways(stair - 1) + ways(stair - 2)
   6. return memo[stair]

2. 2 Count the runs on Example 1

   Now no stair is asked for more than twice: once to work it out, and once more as a memo hit.

   1 + 1 + 2 + 2 + 2 + 1 = 9 calls, down from 15.

   call	ways(5)	ways(4)	ways(3)	ways(2)	ways(1)	ways(0)
   times called	1	1	2	2	2	1

   total

   1 + 1 + 2 + 2 + 2 + 1 = 9 calls

3. 3 Write the count for any n

   Only stairs 2 to n ever do the addition, and each does it once, since later calls hit the memo. Each of those n − 1 additions makes 2 calls. Add the first call:

   1 + 2 × (n − 1) = 2 × n − 1 calls

   Check it with Example 1: 2 × 5 − 1 = 9. That matches the count.

4. 4 Keep only the part that grows fastest

   Drop the 2 and the − 1. What is left is n.

   So the time is O(n).

5. S Space: count the extra memory the same way

   The memo holds up to n − 1 answers, and the call stack is still up to n deep. So the space is O(n).

   memo (n entries)call stack (up to n deep)

Two numbers O(n)

The idea

The memo fills in from the bottom: stair 2, then 3, then 4. So skip the recursion and fill it in that order with a loop. And notice that each stair only needs the two stairs right below it. Once stair k is done, stair k − 2 is never looked at again.

So keep just two numbers: previous for the stair two below, and current for the stair one below. Start with both at 1, for stairs 0 and 1. For each next stair, the new count is previous + current. Then slide: previous takes the old current, and current takes the new count.

Why it is correct: it applies the same rule as the recursion, ways(stair) = ways(stair - 1) + ways(stair - 2), in an order where both right-hand answers are always ready.

Walkthrough

ways

10112345

previouscurrent

previous, current

11

1. previous, current = 1, 1 # stairs 0 and 1
2. for i in 2 .. stairs:
3. previous, current = current, previous + current
4. return current

Work upward instead. Stair 0 and stair 1 each have 1 way. previous and current hold the answers for the last two stairs.

← BackStep →Play1 / 10

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Bottom up with two numbers: build the answers from the ground floor, and
    // keep only the last two, because each stair needs nothing older. O(n) time, O(1) space.
    public int climbStairs(int stairs) {
        // Ways to reach stair 0 and stair 1.
        int previous = 1, current = 1;
        for (int i = 2; i <= stairs; i++) {
            int nextWays = previous + current;
            previous = current;
            current = nextWays;
        }
        return current;
    }
}

Big O

Time O(n)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The loop body does one addition and two moves. That is a fixed job, so each run of the loop counts as 1 step.

   1. previous, current = 1, 1 # stairs 0 and 1
   2. for i in 2 .. stairs:
   3. previous, current = current, previous + current
   4. return current

2. 2 Count the runs on Example 1

   The loop runs once for each stair from 2 to 5.

   4 runs.

   i	2	3	4	5
   loop runs	1	1	1	1

   total

   4 runs

3. 3 Write the count for any n

   The loop goes from 2 to n:

   n − 1 runs

   Check it with Example 1: 5 − 1 = 4. That matches the count.

4. 4 Keep only the part that grows fastest

   Drop the − 1. What is left is n.

   So the time is O(n).

5. S Space: count the extra memory the same way

   Only previous and current are kept, whatever n is. So the space is O(1).

   previouscurrent

Common mistake

Starting from ways(0) = 0

Zero stairs has one way to climb: make no moves. With ways(0) = 0, ways(2) comes out as 1 instead of 2, and every answer after it is too small.

Tested at the limits

2,000 random n from 1 to 20. The plain recursion, the recursion with a memo and the two numbers gave the same answer every time.

Largest inputs	Result
n = 45 (the most allowed), with 1,836,311,903 ways. Two numbers.	Under 0.001 s, and under 0.001 MB of extra memory: just the two numbers.
n = 25. Plain recursion, about 240,000 calls.	0.01 s. Each extra stair makes about 1.6 times more calls, so n = 45 would need almost 4 billion.