Dynamic Programming
Turning exponential brute force into polynomial time by remembering what you've already solved.
- 1 Lesson
Dry-run engine
Climbing Stairs (Tabulation)
Dynamic programming trades a little memory for a lot of time: every subproblem is solved once and kept in a table.
- Input · Stairs
- n = 7
- Output · Returns
- Press play to run it
How it works
You can climb 1 or 2 steps at a time, so dp[i] = dp[i - 1] + dp[i - 2]. Filling the table left to right means every lookup is already computed.
dp_table[8]
- i—
- dp[i-1]—
- dp[i-2]—
- dp[i]—
dp[i] = the number of ways to reach stair i taking 1 or 2 steps at a time. The table is one contiguous block of 8 cells. Seed the base cases: dp[0] = 1 (stand still) and dp[1] = 1 (one single step).
1 / 7
Course Contents
Related courses
- ArraysContiguous, indexable memory — the foundation almost every other data structure builds on.12 lessons · 16 problems
- StringsCharacter arrays with their own set of classic patterns — two pointers, sliding window, and more.19 lessons · 19 problems
- Linked ListNodes linked one direction by pointers instead of contiguous memory.4 lessons · 12 problems