Dynamic Programming

Climbing Stairs

The problem: you are climbing a staircase with n stairs. From each step you can climb either 1 or 2 stairs. How many distinct ways are there to reach the top?

This lesson won't tell you the answer. You'll build it. Six beats, each unlocked by the one before: play the game, discover the rule hiding in your own moves, follow recursive calls, add memory, build the same answers bottom-up, then prove the idea travels beyond staircases.

1

Play the game

Climb 4 stairs using only +1 or +2 moves, and find every distinct route to the top.

start
1
2
3
4
This climb: No moves yet
Ways you've found0 / 5
Climb to the top and your route lands here.

Discover the rule

The pattern is already in the routes you found.

Your goal: group all 5 routes by the size of their very last step.

How to read a route

1 · 1 · 2means climb +1, then +1, then +2.

The final number is 2, so this example belongs in +2 last.

1

Select a route

Look at the number after its final dot.

0 / 5 sorted

Start here: tap any route above.

2

Choose its ending

The two groups activate after you select a route.

Finish beat 1 to unlock

Follow recursion

Run the recurrence as function calls and find the repeated work.

Recurrence

The rule says what an answer depends on:

f(n) = f(n-1) + f(n-2)

Recursion

The code follows that rule by calling itself until it reaches f(0) or f(1).

function ways(n) {
  if (n <= 1) return 1;
  return ways(n - 1) + ways(n - 2);
}

Run the recursive code for f(5). Tap a yellow call to reveal the calls it makes. Keep going until the tree is complete.

1 / 15 calls
f(5)

Finish beat 2 to unlock

Add memory

Use a cache to stop repeated recursive calls.

Start with the big question

Recursion still starts at f(5) and asks smaller questions. This time it carries a cache so an answer can be saved and reused.

Current call stack

f(5)f(4)f(3)f(2)

Top-down means we began with f(5) and followed its smaller dependencies.

Cache

memo[0]
1
memo[1]
1
memo[2]
?
memo[3]
?
memo[4]
?
memo[5]
?

The base cases start filled because their answers are already defined.

Decision 1 of 3

Recursion requests f(2). What should it do?

memo[2] is empty

Finish beat 3 to unlock

Build bottom-up

Compute the same saved answers in order, without recursion.

New task: build the same answers without recursive calls

Memoization is top-down

Start at f(5), recurse downward, and save answers as they return.

Tabulation is bottom-up

Start at dp[0], then fill each answer after its dependencies.

Both methods store the same meaning: the number of ways to reach each stair. Only the order changes.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

Before you fill: two starting facts

Given base cases

The recurrence needs somewhere to start, so these first two cells are defined before we calculate anything:

dp[0] = 1

One way to climb 0 stairs: take no steps.

This “do nothing” path is called the empty route, and it counts as one valid starting route.

dp[1] = 1

One way to climb 1 stair: take a single +1 step.

Why dp[0] matters: at dp[2], it counts the direct 0 → 2 route made by one +2 step.

i=0
i=1
i=2
i=3
i=4
i=5
1
1
2
3
5
8
climbStairs.ts
  1. 1function climbStairs(n) {
  2. 2 const dp = [1, 1];
  3. 3 for (let i = 2; i <= n; i++) {
  4. 4 dp[i] = dp[i - 1] + dp[i - 2];
  5. 5 }
  6. 6 return dp[n];
  7. 7}
Base caseComputedAnswer / dependency arrow

Finish beat 4 to unlock

Make it transfer

If it only works on stairs, you learned nothing.

Variation 1: you can now climb 1, 2, OR 3 steps at a time. What's the recurrence?

Variation 2: stair k is broken; you can't step on it. What changes in the table?

Variation 3: each stair i now has a cost[i] you pay when you step on it, and you want the CHEAPEST way to the top. What's the recurrence?

Final check: what stays the same between memoization and tabulation?

Finish beat 5 to unlock

The pattern, formally

The recurrence: to reach stair i, you either came from stair i-1 (one step) or stair i-2 (two steps). So dp[i] = dp[i-1] + dp[i-2] with dp[0] = dp[1] = 1. This is the Fibonacci pattern. Naive recursion follows the rule but repeats subproblems. Memoization and tabulation both store those answers, reducing the work to O(n).

Naive recursion

Start at f(n), call smaller problems, and store nothing.

O(2ⁿ) time

O(n) call stack

Memoization

Start at f(n), recurse on demand, and cache each answer.

O(n) time

O(n) cache plus call stack

Tabulation

Start at the base cases and fill answers in dependency order.

O(n) time

O(n) table, reducible to O(1)

Takeaways

  • The recurrence isn't handed down. It falls out of grouping paths by their last move. That grouping trick is the reusable skill.
  • A recurrence is the dependency rule. Recursion is one way to execute that rule by calling the same function on smaller inputs.
  • Memoization is top-down dynamic programming: keep recursion, cache each answer, and reuse it on repeated calls.
  • Tabulation is bottom-up dynamic programming: fill the same answers in dependency order with a loop.
  • For climbing stairs, both optimized approaches take O(n) time. Tabulation can use O(1) space by keeping only the previous two answers.
  • New problem? Re-derive: what was the last decision, what are the buckets, how do they combine.