Leetcode 70. Climbing Stairs

Problem

Leetcode 70 - Climbing Stairs

Example:

Input: n = 2
Output: 2

Input: n = 3
Output: 3

Approach

We can use dynamic programming to solve this problem. We will use a list to store the number of ways to reach the i-th step. We will initialize the list with 1 and 2, because there are 2 ways to reach the 1st and 2nd step. Then we will iterate through the list, and for each step, we will add the number of ways to reach the current step to the number of ways to reach the next step.

Visualization of the approach:

1 -> 1 since there is only 1 way to reach the 1st step
2 -> 2 since there are 2 ways to reach the 2nd step (1 + 1, 2)
3 -> 3 since there are 3 ways to reach the 3rd step (1 + 1 + 1, 1 + 2, 2 + 1)
4 -> 5 since there are 5 ways to reach the 4th step (1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 2 + 1, 2 + 1 + 1, 2 + 2)
5 -> 8 since there are 8 ways to reach the 5th step (1 + 1 + 1 + 1 + 1, 1 + 1 + 1 + 2, 1 + 1 + 2 + 1, 1 + 2 + 1 + 1, 2 + 1 + 1 + 1, 2 + 2 + 1, 2 + 1 + 2, 1 + 2 + 2)
...

from the pattern, we can see that the number of ways to reach the i-th step is the sum of the number of ways to reach the (i-1)-th step and the number of ways to reach the (i-2)-th step.

Here is the Python code for the solution:

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        dp = [0] * (n + 1)
        dp[1] = 1
        dp[2] = 2
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]

Time Complexity and Space Complexity

Time Complexity: $O(n)$ since we are iterating through the list n times.

Space Complexity: $O(n)$ since we are maintaining a list of size n.