70. Climbing Stairs#

Difficulty: Easy

Link to Problem: To see the Climbing Stairs problem on LeetCode, click here!

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?

Constraints:

  • 1 <= n <= 45

Probelm Explanation:#

The “Climbing Stairs” problem is a classic algorithmic problem that asks you to find the number of distinct ways to climb a staircase with a given number of steps. Here’s the problem statement:

You are given a staircase with ‘n’ steps. Each time you can either climb 1 step or 2 steps. You need to find out how many distinct ways there are to reach the top of the staircase.

For example, if ‘n’ is 2, there are two ways to climb to the top:

  1. Climbing two steps at once.

  2. Climbing one step, and then another step.

If ‘n’ is 3, there are three ways:

  1. Climbing one step, then one step, and finally one step.

  2. Climbing one step, then two steps.

  3. Climbing two steps, then one step.

The problem essentially asks you to find a solution that counts the possible combinations of 1-step and 2-step climbs that can be taken to reach the top of the staircase. It’s a classic example of a dynamic programming problem where you can break it down into smaller subproblems and build a solution incrementally, as shown in the code I provided earlier.

Solution:#

Here’s a Python function to implement this algorithm:

class Solution:
    def climbStairs(self, n: int) -> int:
        # If there are 1 or 2 steps, there are exactly n ways to reach the top.
        if n <= 2:
            return n

        # Create an array to store the number of ways to reach each step.
        dp = [0] * (n + 1)

        # There is one way to reach the first step (base case).
        dp[1] = 1

        # There are two ways to reach the second step (base case).
        dp[2] = 2

        # Calculate the number of ways to reach each step from the previous steps.
        for i in range(3, n + 1):
            # The number of ways to reach step 'i' is the sum of the ways to reach
            # the previous two steps, as you can take 1 or 2 steps at a time.
            dp[i] = dp[i - 1] + dp[i - 2]

        # The result is the number of ways to reach the top, which is stored in dp[n].
        return dp[n]

Explanation:#

The code defines a class Solution with a method climbStairs that takes an integer n as input and returns the number of distinct ways to climb a staircase with n steps.

  1. If n is 1 or 2, the function returns n directly because there are only 1 or 2 distinct ways to reach the top in those cases.

  2. For n greater than 2, the code uses dynamic programming to calculate the number of ways to reach each step. It creates an array dp of length n + 1 to store these values.

  3. The dp[1] and dp[2] are initialized to 1 and 2, respectively. This is because there is only one way to reach the first step (by taking 1 step), and there are two ways to reach the second step (by taking 2 steps or two 1-step climbs).

  4. The code then uses a loop to fill in the dp array for steps 3 and above. For each step i from 3 to n, it calculates the number of ways to reach that step by adding the number of ways to reach the previous two steps, as you can either take 1 step or 2 steps at a time.

  5. Finally, the function returns the value stored in dp[n], which represents the total number of distinct ways to climb the staircase with n steps.

Test cases:#

Here’s how you can use this solution:

# Example 1:
n = 2
solution = Solution()
print(f"Example 1 - Input: n = {n}, Output: {solution.climbStairs(n)}")  # Output should be 2

Example 1 - Input: n = 2, Output: 2

# Example 2:
n = 3
print(f"Example 2 - Input: n = {n}, Output: {solution.climbStairs(n)}")  # Output should be 3

Example 2 - Input: n = 3, Output: 3

Time and Space Complexity Analysis#

Time Complexity: The time complexity of the solution is O(n) because we use a single for loop that iterates from 3 to n to fill the dp array. In each iteration, we perform constant time operations (addition and assignment). Therefore, the time complexity is linear with respect to the input value n.

Space Complexity: The space complexity of the solution is O(n) as well. We use an array dp of length n + 1 to store the number of ways to reach each step. The size of this array is directly proportional to the input value n, which makes the space complexity linear in terms of n. The rest of the variables used in the function (e.g., i) occupy constant space and do not contribute significantly to the overall space complexity.

In summary, the time complexity is O(n), and the space complexity is O(n) for this dynamic programming solution to the “Climbing Stairs” problem.

Challenging Exercises:#

  1. Generalized Step Sizes: Instead of being limited to 1 step or 2 steps, consider a scenario where you can take steps of sizes [1, 2, 3]. Implement a function that calculates the number of ways to climb the staircase with these different step sizes.

  2. Minimize Steps: Given an integer n, find the minimum number of steps required to reach the top of the staircase. Return both the minimum number of steps and the specific sequence of steps taken.