The problem
A footbridge has n steps. Each move takes you up 1, 2 or 3 steps. Return the number of different sequences of moves that take you from the bottom to exactly the top.
count_ways(3) # 4: 1+1+1, 1+2, 2+1, 3
count_ways(4) # 7
count_ways(0) # 1: the empty sequence
Limits
nis up to 10,000. The answer has thousands of digits; Python’s whole numbers can hold it exactly.
Builds on RECR-3 Recursion trees and RECR-6 Recursion to iteration.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
5 tests, not run yet
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | Small heights | Not run | |
| 2 | Height 0 | Not run | |
| 3 | Height 10 | Not run | |
| 4 | Height 35 | Not run | |
| 5 | Height 10,000 | Not run |