Coders Crushby Napplied AI
Back to DSA Problems
EasyLeetCode #70Dynamic Programming

Climbing Stairs

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?

Constraints
1 <= n <= 45
Coders Crushby Napplied AI

The ultimate interview preparation platform. Master System Design, DSA, and tackle community challenges to crush your FAANG interviews.

System Design

  • All Problems
  • Easy
  • Hard

DSA

  • All Problems
  • Dynamic Programming
  • Graphs

More

  • Problems Arena
  • Growth Paths
  • AI Discovery

Coders Crush by Napplied AI - Built for engineers preparing for FAANG/MAANG interviews

Examples
Input: n = 3
Output: 3
1+1+1, 1+2, 2+1
Solution

Approach

DP where dp[i] = dp[i-1] + dp[i-2]. Ways to reach step i = ways from step i-1 (1 step) + ways from step i-2 (2 steps). This is Fibonacci.

def climbStairs(n):
    if n <= 2:
        return n
    prev, curr = 1, 2
    for _ in range(3, n + 1):
        prev, curr = curr, prev + curr
    return curr
Complexity
Time:O(n)
Space:O(1)
Hints
  • 1.Think about the last step: 1 or 2
  • 2.Relate f(n) to f(n-1) and f(n-2)
  • 3.This is Fibonacci sequence
Asked at
GoogleAmazonAppleMicrosoft