Blind 75.16 - Climbing Stairs

Climbing stairs.

Problem description

Taken directly from LeetCode.

You are climbing a staircase. It takes n steps to reach the top.

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

Example 1:

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

1. 1 step + 1 step \
2. 2 steps

Example 2:

Input: n = 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

Constraints:

• 1 <= n <= 45

Solution type

Caching (all DP problems are fundamentally based on caching).

Solution

Ah, the classic DP problem. Honestly, I’ve come to enjoy these; DP is just caching and it’s always satisfying to use caching to solve something.

The recurrence relation is simple: the number of ways to get to step i is the number of ways to get to step i - 1 plus the number of ways to get to step i - 2.

You can easily do a top-down or bottom-up approach with some sort of memo, but since each step only requires us to take one look at the previous two steps back, we can keep memory usage to two variables in a bottom-up approach. (If you want, you can think of us as keeping a two-element “sliding window” memo.) Friendly reminder that DP doesn’t always mean creating an array, and that therefore, DP can be applied in scenarios that aren’t so intuitive.

int climbStairs(int n) {
    // at init, previous := num ways to get to step 0,
    // current := num ways to get to step 1
    int previous = 1, current = 1;
    for (int i = 1; i < n; ++i) {
        int next = previous + current;
        previous = current;
        current = next;
    }
    return current;
}

These will get harder and the recurrence won’t be nearly as obvious later on.