Pattern: Climbing Stairs: Intro to Dynamic Programming
easyNot solved yet
The problem
A staircase has n steps. Each move, you climb either 1 step or 2 steps. Write a function that returns how many different sequences of moves get you from the bottom to exactly the top. n is between 0 and 40. For n = 0 there's exactly one way: do nothing.
text
1climb_ways(3) -> 3
2climb_ways(5) -> 8
3climb_ways(0) -> 1
For 3 steps, the ways are 1+1+1, 1+2 and 2+1.
Write climb_ways(n) in Python or climbWays(n) in JavaScript.
Runs privately in your browser. Nothing is sent to a server.Ctrl/⌘ + Enter to run · Esc then Tab to leave the editor
Write your function, then run it against 12 tests.
Breakdown
Stuck? Reveal one step at a time, and try again after each one.
Think about the last move
Every way to reach step n ends with either a 1-step move (from step n - 1) or a 2-step move (from step n - 2). Those two groups don't overlap, and together they cover everything.
Step 2
The recurrence
So ways(n) = ways(n - 1) + ways(n - 2), with ways(0) = 1 and ways(1) = 1.
Step 3
Why plain recursion is too slow
Calling ways(n - 1) and ways(n - 2) recursively recomputes the same values again and again: the number of calls grows exponentially. At n = 40, that's hundreds of millions of calls.
Step 4
Compute each value once
Build up from the bottom: start with the answers for 0 and 1, and repeatedly add the last two. You only ever need the last two numbers, so two variables are enough.
Step by step1 / 5
0
1
2
3
4
5
ways
1
1
Start with the base cases.
Solution
Give it a real try first: you learn far more from a wrong attempt than from reading the answer.
Keep two_back = 1 (ways to reach step 0) and one_back = 1 (ways to reach step 1). For each step from 2 to n, the new count is their sum; shift the two variables along. Return one_back (which is also correct for n = 0 and n = 1).
python
1def climb_ways(n):
2 two_back, one_back = 1, 1 # ways to reach step 0 and step 1