Climbing Stairs Leetcode Problem 70 [Python Solution]

Welcome back to another coding adventure!

Today, we're going to tackle the Climbing Stairs problem, which is a classic example of a 1-D Dynamic Programming challenge.

It's rated as an "Easy" problem on LeetCode, making it an ideal starting point for beginners to dive into dynamic programming.

So, let's break down the problem, understand its nuances, and craft an efficient Python solution.

By the end of this guide, you'll be ready to conquer this problem with confidence.

Problem Overview

Question: 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?

Let's illustrate this with a couple of examples:

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

Constraints:
– 1 <= n <= 45

The key idea here is to find the number of distinct ways to reach the top of the staircase.

You can either take 1 step or 2 steps at each stage.

Understanding Constraints

Before we dive into solving the problem, it's essential to understand the constraints.

In this case, n can vary between 1 and 45. This means we need an efficient solution, especially for larger values of n.

Let's keep this in mind as we explore different approaches.

Bruteforce Approach

To solve this problem, we can use a recursive approach.

We'll consider each step at a time, simulating both choices (1 step and 2 steps), and count the number of distinct ways.

Here's the Python code for the bruteforce approach:

def climbStairs(n):
    if n <= 2:
        return n
    return climbStairs(n - 1) + climbStairs(n - 2)

While this code works, it's not the most efficient solution, especially for large values of n.

It involves a lot of redundant calculations, which we'll address shortly with a more optimized approach.

Efficient Approach with Memoization

To optimize our solution, we can use a technique called memoization.

Memoization involves caching the results of expensive function calls and returning the cached result when the same inputs occur again.

This approach significantly reduces redundant calculations.

Here's the Python code for the efficient approach using memoization:

View on GitHub ➹

def climbStairs(n, memo={}):
    if n in memo:
        return memo[n]
    if n &lt;= 2:
        return n
    memo[n] = climbStairs(n - 1, memo) + climbStairs(n - 2, memo)
    return memo[n]

In this code, we store previously computed results in the memo dictionary, which helps us avoid recalculating the same subproblems.

It's a significant improvement in terms of time complexity.

Time and Space Complexity

Time Complexity

The bruteforce approach has an exponential time complexity of O(2^n).

It involves a lot of redundant calculations, making it inefficient for larger values of n.
– The efficient approach with memoization reduces the time complexity to O(n).

This is because we solve each subproblem only once and store the results, avoiding redundant calculations.

Space Complexity

The space complexity of the bruteforce approach is O(n) due to the recursion stack.
The space complexity of the efficient approach with memoization is also O(n) due to the memoization dictionary.

Reasoning Behind Our Approach

Our efficient approach with memoization is based on the idea of breaking down the problem into smaller subproblems and reusing their results.

By doing this, we avoid repetitive calculations and achieve a much faster solution.

Conclusion

In this guide, we've explored the Climbing Stairs problem, understanding its requirements and constraints.

We started with a bruteforce recursive approach, which is intuitive but not efficient for larger inputs.

To optimize our solution, we used memoization to store and reuse the results of subproblems, significantly reducing time complexity.

As a result, our efficient approach has a time complexity of O(n), making it a great choice for solving this problem, even for larger values of n.

If you'd like to try this problem for yourself or review the code, you can find it on LeetCode.

Don't forget to practice and explore more dynamic programming challenges to strengthen your problem-solving skills.

If you have any questions or suggestions, please feel free to comment below.

Happy coding!