LeetCode 70: Climbing Stairs

For one subcategory of dynamic programming problems, the goal is to count the number of ways to do something. For example, in LeetCode 62: Unique Paths, we counted the number of ways a robot could move from the start position to the end position in a grid.

This week, we’ll tackle another counting problem, LeetCode 70: Climbing Stairs. It’s an Easy problem whose solution we’ll adapt to solve a Medium problem next week.

Here’s the Climbing Stairs problem:

You are climbing a staircase. It takes n steps to reach the top. At each position on the staircase, you can take one or two steps. How many ways are there to reach the top?

The examples explain that if n == 2, there are two ways to reach the top: 1) Take one step followed by one step; 2) Take two steps. And if n == 3, there are three ways to reach the top: 1) Take one step, then one step, then one step; 2) Take one step, then two steps; 3) Take two steps, then one step.

Suppose i represents the current position on the staircase. i == 0 is the starting position at the bottom of the staircase (before the first step) and i == n is the ending position at the top of the staircase (after the last step). So if n == 3, it takes three steps to reach the top using the first pattern: climb from position 0 to 1, then from 1 to 2, then from 2 to 3.

Let’s extend the examples to establish more base cases. If n == 1, that means we are standing in front of one step, and once we climb that one step, we’re done. There is only one way to do that. And n == 0 just means a floor with no staircase. For this case, it works best to say that there are 0 ways to climb a staircase with no stairs.

With our base cases defined, we can create our state and state transition. As with many DP counting problems, the key is to think about which actions can be taken at each position. From any stair on the staircase except the last one, we have two options: Take one step or take two steps. After we make that decision, we have the same two options again. So if $f(i)$ represents the number of ways to climb the staircase from step $i$, we can define $f(i)$ recursively as $f(i) = f(i+1) + f(i+2)$. In other words, the number of ways to reach the top from the current step is the number of ways to reach the top by first taking one step, combined with the number of ways to reach the top by first taking two steps.

To generalize our base case rule, we can return $n-i$ when $i \geq n-2$. This wraps up the recursion when we’re near the top of the staircase. And to complete a top-down dynamic programming implementation, we’ll memoize the return value from $f$ to avoid evaluating $f$ multiple times for the same $i$.

Pseudocode

define an int array dp of size n
return count(0, n)

int count(int i, int n)
    // base cases
    if (i >= n-2)
        return n-i

    // check if we already calculated it
    if dp[i] > 0
        return dp[i]

    // two options: one step or two steps
    dp[i] = count(i+1, n) + count(i+2, n)

    return dp[i]

References

Rahul Varma provides implementations using recursion, memoization (top-down), tabulation (bottom-up), and bottom-up with space optimization.

(Image credit: DALL·E 3)

For an introduction to this year’s project, see A Project for 2024.