Climbing Stairs —
The DP array builds Fibonacci from nowhere.
Take 1 or 2 steps at a time — how many distinct ways are there to reach the top of an n-step staircase? This is the classic "bottom-up" DP introduction: build a table from the smallest cases upward, no recursion needed at all. Watch the DP array fill in on LearnBug and see the Fibonacci sequence appear from a problem that has nothing to do with rabbits.
What is the Climbing Stairs problem?
To reach step n, your last move was either a single step from step n-1, or a double step from step n-2. So the number of ways to reach step n is the number of ways to reach n-1 plus the number of ways to reach n-2 — dp[n] = dp[n-1] + dp[n-2]. That recurrence is exactly Fibonacci's, even though nothing about the problem mentions it.
Why visualization helps
Unlike memoized Fibonacci, this version never recurses — it's built entirely from a loop filling an array left to right, one cell at a time. LearnBug shows each cell computed directly from the two before it, so "bottom-up" DP is visibly a different mechanism from top-down memoization, not just a different name for the same thing.
Building the answer from the smallest case up
Start from the trivial cases
dp[0] = 1 (one way to "stay" at the ground — do nothing) and dp[1] = 1 (one way to reach step 1 — a single step). Everything else builds from these two.
Every cell depends only on the two before it
dp[i] = dp[i-1] + dp[i-2]. No recursion, no call stack — just a single forward loop reading two array cells that are already filled in.
Same recurrence as Fibonacci — hidden
This problem never mentions Fibonacci, yet dp = 1, 1, 2, 3, 5, 8... is exactly it. Recognizing a hidden recurrence like this is a core DP skill.
climb_stairs(5) — filling the DP array
dp[0] = 1, dp[1] = 1 — the two base cases, set before the loop starts
One way to be at the ground (do nothing), one way to be at step 1 (a single step). Nothing is computed yet for steps 2 and beyond.
dp[2] = dp[1] + dp[0] = 1 + 1 = 2
To reach step 2, your last move was either a 1-step from step 1 (dp[1] ways) or a 2-step from step 0 (dp[0] ways) — add them together.
dp[3] = dp[2] + dp[1] = 2 + 1 = 3. dp[4] = dp[3] + dp[2] = 3 + 2 = 5
Same rule, applied left to right, each cell only ever looking at the two immediately before it — never anything further back, never recomputing anything already filled in.
dp[5] = dp[4] + dp[3] = 5 + 3 = 8
The loop finishes, and dp[5] holds the answer. Notice the full array — 1, 1, 2, 3, 5, 8 — is exactly the Fibonacci sequence, arrived at without ever writing the word "Fibonacci."
Return: dp[5] = 8 ✓ 8 distinct ways to climb a 5-step staircase
Bottom-up DP array
def climb_stairs(n):
dp = [0] * (n + 1)
dp[0] = 1 # one way to be at the ground: do nothing
dp[1] = 1 # one way to reach step 1: a single step
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2] # last move was 1 step, or 2 steps
return dp[n]
print(climb_stairs(5)) # 8Complexity Notes
Frequently asked questions
Why does the last move (1 step vs 2 steps) determine the recurrence?
Every path to step n has exactly one last move, and that move was either a 1-step (coming from step n-1) or a 2-step (coming from step n-2) — there's no third option. Since these two cases are mutually exclusive and cover every possibility, the total number of ways to reach step n is simply the sum of the ways to reach n-1 and the ways to reach n-2.
Why is this the same recurrence as Fibonacci?
Both are defined by "the current value is the sum of the two before it," with matching base cases (dp[0]=1, dp[1]=1 here lines up with fib(1)=1, fib(2)=1 in a 1-indexed Fibonacci sequence). This is a common DP pattern: many seemingly unrelated counting problems reduce to Fibonacci or a close variant once you find the recurrence.
Could I solve this with memoized recursion instead of a DP array?
Yes — climb_stairs(n) = climb_stairs(n-1) + climb_stairs(n-2) with memoization would give the identical O(n) time complexity. The bottom-up array version is shown here specifically because it avoids recursion and the call stack entirely, which is the more common approach once you're comfortable with the top-down/memoized version.
How would this change if you could also take 3 steps at a time?
The recurrence extends naturally: dp[i] = dp[i-1] + dp[i-2] + dp[i-3], since the last move now has three possibilities instead of two. This pattern — the recurrence's shape following directly from "what were the possible last moves?" — generalizes to any fixed set of step sizes.
Watch the DP array fill in, one cell at a time
Paste climbing stairs into LearnBug and see each value build directly from the two before it.