Skip to content

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
python
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
python
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
python
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)

Comments

No comments yet. Be the first to comment!