DPDynamic Programming
Climbing Stairs (tabulation)
Count the ways to reach step n taking 1 or 2 steps at a time — a Fibonacci recurrence in disguise.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| 1 | 1 | · | · | · | · | · | · | · |
1/16Base cases: there is 1 way to stand on step 0 (do nothing) and 1 way to reach step 1 (a single step).
Cell being filledDependency readBase caseComputedReconstructed choice
PseudocodeLearn Climbing Stairs →
1dp[0] = 1; dp[1] = 12for i in 2 .. n:3 dp[i] = dp[i-1] + dp[i-2]4return dp[n]Variables
n8
Complexity
best O(n)
avg O(n)
worst O(n)
space O(1)
Speed