visual walkthrough
Climbing Stairs
The 'hello world' of DP.
The idea
To stand on step n you either came from step n − 1 or from step n − 2. So the number of ways to reach n is the sum of the ways to reach those two steps.
Written as plain recursion this repeats the same sub-questions again and again. Storing each answer the first time turns an exponential amount of work into a single pass.
Complexity
| approach | time | space |
|---|---|---|
| Plain recursion | O(2ⁿ) | O(n) |
| Dynamic programming | O(n) | O(n) |