Staircase Paths
Easy1-D Dynamic ProgrammingFree
Problem
A staircase has n steps. Each move you climb either one step or two steps.
Return the number of distinct move sequences that take you from the ground (step 0) to exactly step n. Two sequences are different if they differ at any position, so 1+2 and 2+1 count separately.
Example 1
- Input:
- n = 3
- Output:
- 3
1+1+1, 1+2 and 2+1.
Example 2
- Input:
- n = 5
- Output:
- 8
The counts for n = 1, 2, 3, 4, 5 are 1, 2, 3, 5, 8.
Constraints
- 1 ≤ n ≤ 45
- The answer fits in a 32-bit signed integer.
Hint
Show the first hint
Think about the very last move of any sequence that ends on step n.
Walkthrough
How to approach it
01Clarify before coding
- Does order matter? Yes: 1+2 and 2+1 are two different sequences.
- What is the answer for n = 1? One sequence, a single 1-step.
- How large can n be? 45, so the answer still fits in 32 bits and no modulo is needed.
02Brute force
Recurse: from step i try a 1-step and a 2-step, count the branches that land exactly on n. Without memoisation the same sub-staircases are recounted over and over.
Cost: O(φⁿ) ≈ O(1.62ⁿ) time: about 1.8 billion calls for n = 45. Adding a memo on i makes it O(n) time and O(n) space.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.