70. Climbing Stairs

EasyLeetCode

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

How to solve the problem

• Recursion with Memoization

class Solution:
    def climbStairs(self, n: int) -> int:
        @cache
        def dfs(i):
            if i <= 1:
                return 1
            return dfs(i - 1) + dfs(i - 2)

        return dfs(n)

• Dynamic Programming

class Solution:
    def climbStairs(self, n: int) -> int:

        f = [0] * (n + 2)
        f[0] = f[1] = 1
        for i in range(n):
            f[i + 2] = f[i + 1] + f[i]
        return f[n]

• Optimized Dynamic Programming

class Solution:
    def climbStairs(self, n: int) -> int:
        f0 = f1 = 1
        for i in range(2, n + 1):
            f = f0 + f1
            f0 = f1
            f1 = f
        return f1

Complexity

• Approach 1 (Recursion with Memoization): Time complexity: O(n), Space complexity: O(n)
• Approach 2 (Dynamic Programming): Time complexity: O(n), Space complexity: O(n)
• Approach 3 (Optimized DP): Time complexity: O(n), Space complexity: O(1)