Leetcode 70 - Climbing Stairs

Table of contents

Problem

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?

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

Explanation/Approach

This problem can be approached using Dynamic Programming. The key is to recognize that the number of ways to climb to the top is the sum of the ways to climb to the step before the last and the step before that. This is because at each step, you can either climb 1 or 2 steps.

1. If you are one step away from the top, you could have gotten there by taking a single step from the second last step.
2. If you are two steps away, you could have reached the top by taking two single steps or one double step.

This forms the basis of the Fibonacci sequence, where dp[i] = dp[i-1] + dp[i-2].

Solution: Dynamic Programming

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1

        dp = [0] * (n + 1)
        dp[1], dp[2] = 1, 2

        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]

        return dp[n]

Time and Memory Complexity

The time complexity is O(n), as we need to fill the array of size n. The space complexity is also O(n) due to the space used by the dp array.

Explanation

The solution initializes a dp array to store the number of ways to climb to each step. It then iteratively fills this array using the relationship dp[i] = dp[i-1] + dp[i-2]. For n = 3, the array dp will be [0, 1, 2, 3], where dp[3] is the answer, indicating 3 distinct ways to climb to the top.

Visual Representation

Consider n = 3:

Step 1: Only 1 way (1 step)
Step 2: 2 ways (1 step + 1 step, 2 steps)
Step 3: dp[2] + dp[1] = 2 + 1 = 3 ways

1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Certainly! Let’s extend the visual representation and explanation for n = 5 steps.

Extended Explanation

For n = 5, we need to calculate the number of distinct ways to climb a staircase with 5 steps. To do this, we use the dynamic programming approach, leveraging the Fibonacci-like pattern that emerges in the problem.

• The base cases are:
  • dp[1] = 1 (only one way to climb one step).
  • dp[2] = 2 (two ways to climb two steps: 1+1 or 2).
• For every step i from 3 to n, the number of ways to reach step i is the sum of the ways to reach step i-1 and step i-2. This is because you can reach step i either from step i-1 by taking one more step, or from step i-2 by taking a two-step jump.

Visual Representation for n = 5

Let’s break down the steps:

• Step 1:
  • Ways to reach: 1 (1 step).
• Step 2:
  • Ways to reach: 2 (1+1, 2).
• Step 3:
  • Ways to reach: dp[2] + dp[1] = 2 + 1 = 3 (1+1+1, 1+2, 2+1).
• Step 4:
  • Ways to reach: dp[3] + dp[2] = 3 + 2 = 5 (1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2).
• Step 5:
  • Ways to reach: dp[4] + dp[3] = 5 + 3 = 8 (1+1+1+1+1, 1+1+1+2, 1+1+2+1, 1+2+1+1, 2+1+1+1, 1+2+2, 2+1+2, 2+2+1).

So, for n = 5, there are 8 distinct ways to climb to the top of the staircase.