Climbing Stairs

Easy📊 1D Dynamic ProgrammingMathDynamic ProgrammingMemoization

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

Pattern Recognition & Intuition

Why this is a 1D Dynamic Programming problem

📊

1D Dynamic Programming

Cache sub-problem answers — never solve the same problem twice.

1D DP stores answers to sub-problems in a 1D array (or a few variables). Each dp[i] represents the answer to a sub-problem of size i. The solution to the full problem is built bottom-up from these smaller answers, eliminating the exponential redundancy of naive recursion.

MENTAL MODEL

Define dp[i] clearly ("what does it mean?"), identify the recurrence relation dp[i] = f(dp[i-1], dp[i-2], …), handle base cases.

INTUITION

Imagine you're climbing stairs. The number of ways to reach step n is ways(n-1) + ways(n-2). If you compute ways(n-1) and ways(n-2) independently by recursion, you recompute ways(1), ways(2), … dozens of times. DP caches them so each is computed exactly once.

SIGNALS — WHEN TO USE THIS PATTERN

"Number of ways to…", "minimum cost to…", "maximum profit from…"
Decisions at each step that depend on prior decisions
Overlapping subproblems: the same sub-problem is solved multiple times in recursion
"You can do X or Y at each step" — classic two-choice DP
Optimal substructure: the optimal answer for i uses optimal answers for i-1, i-2, etc.

Approaches & Trade-offs

From brute force to optimal — understand every step of the journey

BRUTE FORCE

Brute Force

⏱ O(2ⁿ) — exponential due to recomputation of overlapping sub-problems💾 O(n) recursion stack

✦ OPTIMAL

Optimal

⏱ O(n) — each state computed exactly once💾 O(n) for the array; O(1) with space optimization

Build the dp array from smallest sub-problems to largest. No recursion — just a loop.

ALGORITHM STEPS

Identify the DP state: dp[i] = answer for sub-problem i
Initialize base cases: dp[0], dp[1], …
Loop i from 2 to n, computing dp[i] from earlier values
Return dp[n] as the final answer
Space-optimize: if dp[i] only uses dp[i-1] and dp[i-2], store just two variables

TIME

O(n) — each state computed exactly once

SPACE

O(n) for the array; O(1) with space optimization

Always define dp[i] clearly FIRST, then figure out the recurrence.

def climb_stairs(n):
    if n <= 1: return 1
    prev2, prev1 = 1, 1          # dp[0], dp[1]
    for i in range(2, n + 1):
        curr = prev1 + prev2     # dp[i] = dp[i-1] + dp[i-2]
        prev2, prev1 = prev1, curr
    return prev1

Key Insight & Common Pitfalls

THE "AHA" MOMENT

The hardest part of DP is NOT the code — it's the definition of dp[i]. Ask yourself: "What is the sub-problem at index i?" Once that's crystal clear, the recurrence relation usually follows naturally. Common definitions: dp[i] = "max sum ending at i", "min cost to reach i", "number of ways to reach i". Write the definition as a comment before writing any code.

COMMON MISTAKES

✕Undefined dp[i]: not being precise about what dp[i] represents
✕Missing base cases: dp[0] or dp[1] initialized incorrectly
✕Off-by-one: dp has length n vs n+1 — be careful with 0-indexed vs 1-indexed
✕Trying to space-optimize before the O(n) solution works correctly

PRO TIPS

›Top-down with memo: add @functools.lru_cache(None) to your recursive function to auto-memoize
›If dp[i] depends only on the last 1-2 values, use rolling variables (O(1) space)
›"House Robber" pattern: dp[i] = max(dp[i-1], dp[i-2] + nums[i]) — skip or take
›Draw the recursion tree first, identify repeated sub-trees — that's the overlap to cache

Interactive Visualizer

Building 📊 1D Dynamic Programming Visualization

Generating visualization…