Problem 28.1 · DP Foundations: 1DEasy

Climbing Stairs

What it teaches: The first DP: ways(i) = ways(i − 1) + ways(i − 2).

Practise it on judges as “Climbing Stairs”.

The problem

You climb 1 or 2 steps at a time. How many distinct ways are there to reach the top of an n-step staircase?

Example 1

Input: n = 3
Output: 3

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

Constraints

1 ≤ n ≤ 45

Pattern clues in the wording

→ Count the ways
→ Each step depends on the previous one or two

These clues point to 1D Dynamic Programming: Define dp[i] as the answer for the first i items, write how it depends on smaller i, and fill it left to right.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int climbStairs(int n) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	n = 2	2
2	n = 3	3
3	n = 5	8

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Two variables · O(n)2. Memoised recursion · O(n)

Two variables

Time O(n) Space O(1)

prev2 = ways(i − 2), prev1 = ways(i − 1); roll them forward.

Approach 1

class Solution {
    public int climbStairs(int n) {
        int prev2 = 1, prev1 = 1;          // ways(0), ways(1)
        for (int i = 2; i <= n; i++) {
            int cur = prev1 + prev2;
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
}

Verdict: Tabulation with the table shrunk away.

Memoised recursion

Time O(n) Space O(n)

ways(i) = ways(i − 1) + ways(i − 2) with a cache.

Approach 2

class Solution {
    private final int[] memo = new int[46];

    public int climbStairs(int n) {
        if (n <= 1) return 1;
        if (memo[n] != 0) return memo[n];
        return memo[n] = climbStairs(n - 1) + climbStairs(n - 2);
    }
}

Verdict: Same answer top-down.

Before you submit

Edge cases and common mistakes

Test these inputs

n = 1
n = 45 (still fits in int)

Mistakes people make

Plain recursion without memo (TLE for n ≈ 45).

Interview

Follow-up questions

What if you can take 1, 2 or 3 steps, or any step size in a set?

Command Palette