The problem
You are climbing a staircase with n steps. Each move you climb either 1 or 2 steps. In how many different ways can you reach the top?
Input: n = 6 Output: 13
Picture it
Picture the staircase with a number written on each step: the number of different ways to stand on that step. Your last move onto step i came either from step i − 1 (a 1-step) or from step i − 2 (a 2-step). So the ways to reach step i are the two numbers below it added together. We fill the steps from the bottom up.
How to recognise it
- The question is "how many ways" to reach a total, not "which way", so you count outcomes rather than list them.
- Each move comes from a small fixed set (1 step or 2 steps), so the last move into step n can only be one of a few kinds.
- The ways to reach step n are built from the ways to reach earlier steps: the same sub-question (ways to reach step k) is asked again and again.
- n is at most 45, a hint that the answer is large (about 1.8 × 10^9) and that listing every route is hopeless.
- The words "different ways" with moves that all add up to a total point to 1-D dynamic programming (DP: solve small cases first and reuse their answers).
Start with brute force
Follow the definition. To reach step n, your last move was either from n − 1 or from n − 2, so add the number of ways to reach each, and recurse down to the base cases.
def climb_brute(n):
if n <= 1:
return 1
return climb_brute(n - 1) + climb_brute(n - 2)
Every call splits into two more calls. The number of calls grows like the answer itself, so time is exponential, roughly O(1.6^n) (the golden ratio to the power n). For n = 45 the answer is 1,836,311,903 and the recursion makes about 3.7 × 10^9 calls, which is far too slow. Space is O(n) for the call stack.
From brute force to the idea
- Find the waste.
climb_brute(5)callsclimb_brute(3)once from 4 and once from 5, and each of those calls repeats the same subtree below it. There are only n + 1 different questions, yet the recursion answers them billions of times. - Remember each answer. Store the answer for every step in a list
ways, whereways[i]is the number of ways to stand on step i. - Fill in order. Steps 0 and 1 each have exactly one way (stay put, or take one step). After that,
ways[i] = ways[i - 1] + ways[i - 2], because the last move was either a 1-step from i − 1 or a 2-step from i − 2. Those two groups of routes never overlap. - Read off the answer.
ways[n]is the result. The numbers are the Fibonacci sequence.
This is the key idea: the count for step i depends only on the two counts just below it, so one left-to-right pass fills the table.
The key idea
ways[i] = ways[i − 1] + ways[i − 2]: the Fibonacci pattern. Only the last two numbers are needed. O(n).
Python solution
def climb(n):
ways = [1, 1] + [0] * (n - 1)
for i in range(2, n + 1):
ways[i] = ways[i - 1] + ways[i - 2]
return ways[n]In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(1.6^n): two calls per call, the same steps are solved over and over | O(n): recursion depth |
| Table (shown code) | O(n): one addition per step | O(n): the ways list (only the last two values are really needed, so O(1) is possible) |
Edge cases
- n = 1: returns
1. The list starts as[1, 1], so the loop does not run. - n = 2: returns
2(1+1 or 2). - n = 3: returns
3; n = 4 returns5. - n = 45 (the largest allowed): returns
1836311903. Python integers never overflow; in a 32-bit language this still fits (below 2^31 − 1 = 2,147,483,647), but n = 46 would not. - n = 0: returns
1(the empty climb). The problem never asks for it, but the list[1, 1]is built so the code does not crash.
Common mistakes
- Starting the loop at 1 instead of 2: for n = 1 it computes
ways[0] + ways[-1], and the index −1 wraps to the end of the list, giving 2 instead of 1. - Setting
ways[0] = 0, which makes every later value 0 or too small. Standing at the start counts as one way. - Using plain recursion without a table, which times out for n in the high thirties and above.
- Allocating a list of size n instead of n + 1, so
ways[n]is out of range.
You may now climb 1, 2 or 3 steps at a time. Count the ways to reach step n. For example, n = 3 has 4 ways (1+1+1, 1+2, 2+1, 3). Describe your approach, then write it if you like.
Compare with our answer
The last move now comes from one of three earlier steps, so the table sums three neighbours instead of two.
def climb_123(n):
ways = [1] + [0] * n
for i in range(1, n + 1):
ways[i] = sum(ways[i - s] for s in (1, 2, 3) if i - s >= 0)
return ways[n]
climb_123(3) is 4, climb_123(4) is 7 and climb_123(5) is 13. Time O(n), space O(n).
A strong answer mentions: the base case ways[0] = 1 (one way to do nothing), summing over every allowed last move, guarding against negative indices for small i, and that the pattern extends to any fixed set of step sizes in O(n × number of sizes).
1. A frog hops 1, 3 or 5 pads at a time. You must count the ways to land exactly on pad n, with n up to 40. Which approach fits best?
The last hop into pad i comes from i − 1, i − 3 or i − 5, so the counts add up in a table. A greedy choice finds only one route, not the number of routes, and searching or two pointers do not apply because nothing is sorted or paired.
2. Why does the shown loop run in O(n) while the brute force recursion is exponential?
There are only n + 1 different questions, and the table answers each once. The recursion asks the same question repeatedly (about 3.7 × 10^9 calls for n = 45). Memory per call and integer width are not the cause.
3. A learner changes the loop to for i in range(1, n + 1): and keeps everything else. For which input is the result wrong?
For n = 1 the list is [1, 1], so ways[1] becomes ways[0] + ways[-1] = 2 instead of 1. For n ≥ 2 the list ends in 0, so the wrapped read adds 0 and ways[1] stays 1; the results for 2, 3 and 45 are still correct.
Score 60% or more and the lesson is marked complete.