Climbing Stairs Problem in Python

Posted On May 6, 2023

The climbing stairs problem is a classic dynamic programming problem that asks how many distinct ways there are to climb n stairs if you can take 1 or 2 steps at a time. This problem has practical applications in many areas, including computer science, finance, and physics. In this post, we will explore how to solve the climbing stairs problem using Python.

Understanding the Problem

Before we start coding, let’s take a moment to understand the problem. Suppose you have a staircase with n steps. You can climb the staircase by taking 1 or 2 steps at a time. For example, if n=3, there are three distinct ways to climb the stairs:

1. Take 1 step, then 1 step, then 1 step.
2. Take 1 step, then 2 steps.
3. Take 2 steps, then 1 step.

Our goal is to write a function that takes an integer n as input and returns the number of distinct ways to climb the stairs.

Solution

The key to solving the climbing stairs problem is to recognize that it can be solved using dynamic programming. Specifically, we can use a dynamic programming array dp where dp[i] represents the number of distinct ways to climb i stairs. We can initialize dp[0]=1 and dp[1]=1 since there is only one way to climb 0 or 1 stairs. For any value of i > 1, we can use the recursive formula:

dp[i] = dp[i-1] + dp[i-2]

This formula states that the number of ways to climb i stairs is equal to the sum of the number of ways to climb i-1 stairs and the number of ways to climb i-2 stairs. This is because we can either take 1 step from the i-1th stair or 2 steps from the i-2nd stair to reach the ith stair.

Here’s the Python code to implement the solution:

def climb_stairs(n: int) -> int:
    dp = [1, 1]
    for i in range(2, n+1):
        dp.append(dp[i-1] + dp[i-2])
    return dp[n]

In this code, the climb_stairs function takes an integer n as input and returns the number of distinct ways to climb n stairs. We initialize dp with dp[0]=1 and dp[1]=1, then use a for loop to fill in the rest of the array using the recursive formula. Finally, we return dp[n], which is the number of distinct ways to climb n stairs.

Example

Let’s test the climb_stairs function with an example. Suppose we want to climb 4 stairs. According to the formula, the number of distinct ways to climb 4 stairs is equal to the sum of the number of ways to climb 3 stairs and the number of ways to climb 2 stairs. We can verify this result using the climb_stairs function:

>>> climb_stairs(4)
5

This result is correct: there are 5 distinct ways to climb 4 stairs.

Conclusion

The climbing stairs problem is a classic dynamic programming problem that asks how many distinct ways there are to climb n stairs if you can take 1 or 2 steps at a time. We can solve this problem using a dynamic programming array where dp[i] represents the number of distinct ways to climb i stairs. We initialize dp[0]=1 and dp[1]=1 and use a recursive formula to fill in the rest

of the array. The formula is dp[i] = dp[i-1] + dp[i-2], which states that the number of ways to climb i stairs is equal to the sum of the number of ways to climb i-1 stairs and the number of ways to climb i-2 stairs. We can then use a for loop to fill in the rest of the array and return dp[n], which is the number of distinct ways to climb n stairs.

The climbing stairs problem has many practical applications. For example, it can be used to model the behavior of stock prices, where each step represents a change in price. It can also be used to model the behavior of particles in a physical system, where each step represents a change in position or energy level. In computer science, the climbing stairs problem can be used to analyze the complexity of algorithms, as it is a common example of a dynamic programming problem.

It’s worth noting that there are alternative solutions to the climbing stairs problem. One approach is to use matrix exponentiation to compute the nth Fibonacci number, which is equal to the number of distinct ways to climb n stairs. This approach has a time complexity of O(log n), which is faster than the O(n) time complexity of the dynamic programming solution. However, the matrix exponentiation approach is more complex and requires a deeper understanding of linear algebra.

The climbing stairs problem is a classic dynamic programming problem that can be solved using a dynamic programming array and a recursive formula. This problem has many practical applications and can be used to model the behavior of complex systems in various fields. By understanding the climbing stairs problem and its solution, you can develop a deeper appreciation for the power and flexibility of dynamic programming.