Day 2 : 70. Climbing Stairs

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?

Before we get started let's take a deep breath…

It took me some good time to wrap my head around this problem, so if I don’t explain it perfectly, just know that's on me, not on you.

Alright, let’s break it down together before we dive into the code.

• What are we asked? Number of different ways to climb a staircase

• How many stairs to we climb with each step?: 1 or 2 stairs.

• How long is the staircase? It has n stairs

Let's look at an example with n = 4.

The ways we can climb the stairs are:

1. 1 + 1 + 1 + 1 = 4

2. 1 + 2 + 1 = 4

3. 1 + 1 + 2 = 4

4. 2 + 2 = 4

That’s 4 distinct ways to climb a 4-step staircase with steps of 1 or 2 stairs.

If we tried to brute-force every possible combination of 1’s and 2’s, that would be A LOT OF WORK, since n gets larger. This would increase the problem complexity exponentially!

Instead, we can use a dynamic programming (DP) approach to break the problem into smaller, easier-to-solve parts. Specifically, we are going to use memoization!

No worries! The name might sound strange, but I promise it’s simpler than it seems!

Memoization

It's a technique where we “remember” the results of function calls by storing them. When we need the result again, instead of recalculating, we just look it up. This saves time, especially in problems where the same calculations repeat.

Take a look at the following example!

So, how will memoization help with our problem? 🤔

Remember!! In DP, we break down problems into overlapping subproblems, where solutions to some parts of a subproblem can be reused in other subproblems. Memoization lets us store those “some parts” of the solution as we go, so if they come up again in another part, we won't need to recalculate them again!!

So, in our problem we’ll use an array to represent the number of ways to reach each step i. We know that to get to a stair i we must come from another stair i - 1, or i - 2, which represents our overlapping subproblem to calculate!

In DP there's usually 2 ways to tackle a problem:

• In a top-down approach we start by trying to solve the big problem first, and start breaking into subproblems as needed, working our way to the base cases (the smallest subproblems).

• In a bottom-up solution we start by solving the smallest subproblems first (the base cases!) and build up until until we reach the solution for the main problem!

The only difference lies in which subproblems we solve first. In the end, by solving all subproblems we will arrive at a solution for the overall problem.

Top-Down Approach

There's a very basic template for most top-down recursive approaches!

1. Base case: Define when to stop recursion (at the smallest subproblems)!

2. Memoization: If computation was previously done and stored, just retrieve it!

3. Formula: If computation wasn't done before, compute and save result!

Let's use the template:

1. Base case: We know we can get to stair 0 in only one way (we would initially start at stair 0) and get to stair 1 in just also just one way.

2. Memoization: We'll use the array to store the different number of ways to reach every single stair. So, the array will be of size n + 1 (from stair 0 to stair n).

3. Formula: dp[n] = dp[n - 1] + dp[n - 2], so, getting to stair n through either a step of size 1 or a step of size 2.

For example, with n = 4:

Break down the problems:

• dp[4] = dp[3] + dp[2]

• dp[3] = dp[2] + dp[1]

• dp[2] = dp[1] + dp[0]

• dp[1] = 1 (base case)

• dp[0] = 1 (base case)

Build the solution back up:

• dp[2] = 1 + 1 = 2

• dp[3] = 2 + 1 = 3

• dp[4] = 3 + 2 = 5 (answer)

class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(n + 1, -1);
        return climb(n, dp);
    }

    int climb(int n, vector<int>& dp) {
        if (n <= 1) return 1;
        if (dp[n] != -1) return dp[n];
        dp[n] = climb(n - 1, dp) + climb(n - 2, dp);
        return dp[n];
    }

Bottom-Up Approach

Only difference is we will build iteratively from the base cases to bigger problems until we have solved our main problem! So we start by solving our base cases, and up from there!

• dp[0] = 1 (base case)

• dp[1] = 1 (base case)

• dp[2] = dp[1] + dp[0] = 1 + 1 = 2

• dp[3] = dp[2] + dp[1] = 2 + 1 = 3

• dp[4] = dp[3] + dp[2] = 3 + 2 = 5 (answer)

class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};

Resources of the week

• Unsexy products make it first

• Sam Altman’s advice to 23 year olds (minute 23)

Self-hacks of the week

I truly believe you can gaslight yourself to success.

1. What you are looking for is looking for you

2. Start your day with a savory breakfast

Jobs and Scholarships

1. New scholarships of this week!

2. Entry level jobs!!