Climbing Stairs

Count the number of ways to climb n stairs (1 or 2 steps at a time).

Pattern

Fibonacci DP

This problem follows the Fibonacci DP pattern, commonly found in the 1-D Dynamic Programming category. Recognizing this pattern is key to solving it efficiently in an interview setting.

Approach

How to Solve It

dp[i] = dp[i-1] + dp[i-2]. Can optimize to two variables.

Key Insight

This is literally Fibonacci — the number of ways to reach step n is the sum of ways to reach n-1 (one step) and n-2 (two steps).

Step-by-step

1Base cases: dp[0] = 1, dp[1] = 1
2For each step from 2 to n: dp[i] = dp[i-1] + dp[i-2]
3Optimize space by keeping only the last two values

Pseudocode

a, b = 1, 1
for i in range(2, n + 1):
    a, b = b, a + b
return b

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(1)

Master this pattern with YeetCode

Practice Climbing Stairs and similar 1-D Dynamic Programming problems with flashcards. Build pattern recognition through active recall.

Practice this problem

NextHouse Robber →