Step-by-Step Solutions: Exploring LeetCode’s “Climbing Stairs” Problem

Introduction

At first glance, stairs might seem like a mundane part of daily life. But if we view them through the lens of computer science, they can present an engaging puzzle. LeetCode’s “Climbing Stairs” problem (#70) turns this everyday activity into a classic combinatorial challenge, rooted in dynamic programming. In this article, we’ll ascend the staircase of this problem and reach the top with a Java solution in hand.

Problem Statement

Climbing Stairs (LeetCode #70): 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?

Approach

This problem can be solved with dynamic programming. Here’s why:

• The number of ways to reach step i is the sum of the ways to reach step i-1 (and take one step) and step i-2 (and take two steps).

We can set up an array where each index represents a step and its value represents the number of ways to reach that step.

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

        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }

Explanation

• If there are only 1 or 2 stairs, the number of ways to climb them is the same as their count.
• We initialize an array dp of size n + 1 to store the number of ways to reach each step.
• We know the ways to reach the first and second steps, so we fill dp[1] and dp[2] accordingly.
• For each subsequent step, the number of ways to reach it is the sum of the ways to reach the two preceding steps.
• Finally, dp[n] it gives us a number of ways to reach the top.

Conclusion

The “Climbing Stairs” problem showcases the beauty of dynamic programming. By breaking down the problem into smaller, more manageable sub-problems, we can efficiently compute the number of ways to reach the top of the staircase. This problem serves as a foundational exercise in understanding the principles and applications of dynamic programming in algorithmic challenges.