Solving the Climbing Stairs Problem on Leetcode

The “Climbing Stairs” problem is a great intro to dynamic programming problem. In this post, I will walkthrough how to end up at the solution.

Problem Description

The problem statement is the following:

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?

The examples given are the following:

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

The constraints given are the following:

• 1 <= n <= 45

Approach

When dealing with dynamic programming problems, start off by trying to identify a recurrence relation or pattern in the problem that can be used to build a solution incrementally. In this case, let’s analyze the problem step by step:

1. For the base cases:

• When n = 0, there's one way to climb the staircase: by doing nothing.
• When n = 1, there's also one way to climb: by taking one step.
• When n = 2, there are two ways: either by taking two 1-step moves or a single 2-step move.

2. For n > 2, let's consider the last step:

• If you took a single step as your last move, then the number of ways to reach the n-th step is the same as the number of ways to reach the (n-1)-th step.
• If you took a double step (2) as your last move, then the number of ways to reach the n-th step is the same as the number of ways to reach the (n-2)-th step.

Based on the analysis above, we can conclude that the number of ways to reach the n-th step is the sum of the number of ways to reach the (n-1)-th step and the number of ways to reach the (n-2)-th step. This forms the basis for our dynamic programming solution.

To make things crystal clear, let’s look at an example of climbing three steps. If you finish with one step, you could either take three 1-step moves or one 2-step followed by a 1-step. It’s the same number of options as the (n-1)-step or the second step. If you finish with a 2-step, you can only start with a 1-step and finish with a 2-step. This is the same number of options as the (n-2)th step or the fist step. So, you have three (2 + 1) ways to get to the third step.

Since the solution for a step only depends on the solutions for the two steps before it, you only need to remember those two values. Let’s call those variables one and two. Then, we'll iterate through the number of stairs until we reach our goal number, calculating the number of ways to reach that step and adjusting the variables as needed.

The Code

The code looks as follows:

class Solution:
    def climbStairs(self, n: int) -> int:
        one, two = 1, 1
        for i in range(n-1):
            tmp = one
            one += two
            two = tmp
        return one

Here you can see that for every stair number, we are calculating the number of ways to get there by adding up the ways of the two previous stairs before it and then ultimately returning the solution for stair n.

Time Complexity

The time complexity of this solution is O(n) since we only have a single loop that iterates through the steps. The dynamic programming approach allows us to optimize the problem and avoid redundant calculations, making it an efficient solution for larger values of n.

Conclusion

In this blog post, we’ve covered how to solve the “Climbing Stairs” problem on LeetCode using dynamic programming. We explained the method and shared a solution that makes tackling the challenge straightforward. Plus, with our approach, we keep things efficient — it runs in O(n) time. So, now you have a tool to conquer any staircase with ease and efficiency.