Climbing Stairs — Coding Interview Question

Let’s understand and solve this LeetCode problem which falls into 1D array category of dynamic programming problems.

Let’s dive into the world of dynamic programming by tackling the popular Climbing Stairs problem from LeetCode. Whether you’re a seasoned developer, a computer science student, or a coding enthusiast, this post aims to provide an in-depth understanding of the Climbing Stairs problem and its solution.

Problem Statement

Let’s first understand the problem at hand. Here’s the problem statement 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?

Understanding the Problem

Let’s take an example. If we have a staircase with 3 steps, there are 3 distinct ways to get to the top:

1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

So, the output for input n = 3 is 3.

Brute Force Approach

A straightforward approach to solving this problem is to use recursion. Let’s understand why!

Base Case

Base cases are the situations where we know the answer without needing to do any computations.

In our climbing stairs problem, the base cases are:

1. If you’re on the first step, there’s only one way to reach there from the bottom.
2. If you’re on the second step, there are two ways: you can either take two single steps or one double step.

Recursive Case

The recursive case is like standing on any other step and figuring out how to reach there. It’s where we take the problem and break it down into smaller versions of the same problem.

For our climbing stairs problem, the recursive case is:

• If you’re on any other step (let’s say the 3rd, 4th, 5th step, and so on), you can reach there either from the step immediately below it or from the step two steps below.
• So, the total ways to reach your current step is the sum of the ways to reach the two steps below.

So, the essence of recursion lies in defining how to break the problem down into smaller pieces (the recursive case), and identifying the simplest pieces that we know the answers to (the base cases). By combining these pieces together, we can solve the original problem.

public class Solution {
    public int climbStairs(int n) {
        // Base cases
        if (n <= 2) return n;

        // Recursive call
        return climbStairs(n - 1) + climbStairs(n - 2);
    }
}

However, this approach has a significant problem — it’s very slow! Because we’re calling climbStairs twice for each step, the time complexity of this solution is O(2^n). And, we're recalculating the same values many times.

Refer to the post Dynamic Programming — Demystified, for detailed explanation of the key characteristics of dynamic programming such as: overlapping sub-problems and optimal substructure.

Top-Down Dynamic Programming Approach (Memoization)

To improve our solution, we can use a technique called memoization to store the result of each sub-problem. Then, before doing any computation, we can first check if we've already solved this sub-problem. If we have, we simply return the stored result.

Memoization eliminates the redundant computation and improves our algorithm's efficiency.

Here is the Java solution using top-down dynamic programming:

public class Solution {
    public int climbStairs(int n) {
        // Create memoization table
        int[] memo = new int[n + 1];

        // Initialize memoization table with -1
        Arrays.fill(memo, -1);

        // Call recursive helper function
        return climb(n, memo);
    }

    private int climb(int n, int[] memo) {
        if (n <= 2) return n;

        // If the result is already in the memoization table, return it
        if (memo[n] != -1) return memo[n];

        // Otherwise, compute the result and store it in the memoization table
        memo[n] = climb(n - 1, memo) + climb(n - 2, memo);

        return memo[n];
    }
}

This solution significantly reduces our time complexity to O(n), but it’s still not the most efficient approach. Why? Because we’re using recursion, which takes up space on the call stack and can lead to a stack overflow for large inputs.

Bottom-Up Dynamic Programming Approach (Tabulation)

We can eliminate the risk of stack overflow and further improve our solution by using a bottom-up dynamic programming approach. This approach involves building up the solution iteratively. We start with the smallest sub-problems and solve larger sub-problems using the solutions of the smaller ones.

public class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;

        int[] ways = new int[n + 1];

        // base cases
        ways[1] = 1;
        ways[2] = 2;

        // fill the ways array in bottom-up manner
        for (int i = 3; i <= n; i++) {
            ways[i] = ways[i - 1] + ways[i - 2];
        }

        // return the final result
        return ways[n];
    }
}

Understanding Bottom-Up Strategy: The Reverse Journey

In the top-down approach or recursion, we start from the ‘top’ of the problem (i.e., the entire staircase or the final step) and break it down into smaller, simpler ‘sub-problems’ (i.e., the steps below). We keep solving these sub-problems until we reach the ‘base’ cases (i.e., the first or second step), where we know the answers.

The bottom-up strategy, on the other hand, flips this process on its head. Instead of starting from the top, we start from the base cases and work our way up to the top. It’s like climbing the stairs from the bottom up!

It’s the exact reverse order of the top-down approach. Instead of breaking down the problem from top to bottom, we’re building up the solution from the bottom to the top.

Conclusion

We’ve solved the Climbing Stairs problem using dynamic programming. As you can see, dynamic programming provides a powerful way to break down complex problems into simpler sub-problems, and build up the solution in an efficient and systematic manner.

The core concept behind dynamic programming is to avoid redundant computation by storing and reusing the results of sub-problems, which is exactly what we did.

I hope this post helps you understand not only the solution to the Climbing Stairs problem, but also the core concept behind dynamic programming.

Don’t forget to follow me on medium for more such posts on coding interview problems.