0070.Climbing Stairs

Link: 70. Climbing Stairs
Track: Amazon Tag

Question

Restate the problem

• Given an integer n, you are at step 0 and want to reach step n.
• Each move you can climb 1 or 2 steps.
• Return the number of distinct ways to reach step n.

Edge Case

• n = 1, return 1
• n = 2, return 2

---

Method 1 - dp
Method 2 - dp O(1)

Method01 - dp

Approach

• Key insight: dp[i]=dp[i−1]+dp[i−2]
• Define dp[i] = number of ways to reach step i
  • Base cases:
    • dp[0] = 1
    • dp[1] = 1
  • Fill dp[2..n] using the recurrence

Complexity

• Time Complexity: O(n)
• Space Complexity: O(n)

Code

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

Method02 - dp

Code

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 1:
            return 1
 
        prev2, prev1 = 1, 1  # dp[0], dp[1]
        for _ in range(2, n + 1):
            prev2, prev1 = prev1, prev2 + prev1
 
        return prev1

---

History

• Feb-15-2026 Peeked