You climb n steps, one or two at a time. In how many distinct ways can you reach the top?
Before you code
The last move was either one step or two, so the count is the sum of the counts for n − 1 and n − 2. Write it as recursion, see it slow down around n = 35, then memoize.
Hints
- Base cases: one way for n = 0 (or n = 1) and two for n = 2.
- Memoize with a dictionary or
functools.cache. - Then keep only the last two values in a loop: O(n) time, O(1) space.
Production & complexity notes
When solving Climbing stairs on LeetCode (easy), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Memoization to reinforce the underlying pattern.
What it practices
Overlapping subproblems and the cache that removes them, from Memoization.