Climbing Stairs
A staircase has n steps, and each move advances it by 1 or 2 steps. Count how many distinct ways there are to reach the top.
Do this lesson first: climbing stairsExample input
n = 5
Expected output
8
Break it down
Answer each question out loud before you open it. Getting it wrong here is the useful part — a revealed answer you never guessed at teaches you nothing.
Fill the table
The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.
Press start. The animation stops at every cell YOUR recurrence must fill.
dp[0] = 1 and dp[1] = 1 are given; see the flagship lesson for why standing still counts as one way. Every other cell depends only on smaller indices, so filling left to right guarantees both dependencies exist before they are read.
- 1
function climbStairs(n) { - 2
const dp = [1, 1]; - 3
for (let i = 2; i <= n; i++) { - 4
dp[i] = dp[i - 1] + dp[i - 2]; - 5
} - 6
return dp[n]; - 7
}
The code, the trap, the variations
- 1
function climbStairs(n) { - 2
const dp = [1, 1]; - 3
for (let i = 2; i <= n; i++) { - 4
dp[i] = dp[i - 1] + dp[i - 2]; - 5
} - 6
return dp[n]; - 7
}
Where people go wrong
Setting dp[0] = 0 because standing on the ground feels like doing nothing. But dp[0] means "one way to be already at the top with zero steps left" — one way to stand still — and without it dp[2] comes out wrong: 1 + 1 = 2 only balances if dp[0] contributes.
Allow moves of 1, 2, or 3 steps instead of just 1 or 2.
A third bucket and a third base case join the sum. The state and the left-to-right order are untouched — only how many prior cells the last move can have come from grows.
Give each step a cost to land on it and ask for the cheapest way up instead of the count.
The combine step switches from summing both predecessors to taking the minimum of one, which turns this into Weighted Climbing Stairs — the two cells read stay the same.