1D Dynamic Programming
Build a 1D table bottom-up so each cell reuses already-computed results.
Pattern: dp[i] = f(dp[i-1], dp[i-2], ...)
LC 70 (Climbing Stairs), LC 198 (House Robber), LC 509 (Fibonacci).
Core Idea: Instead of re-computing overlapping subproblems recursively,
we fill a table left-to-right. Each cell depends only on cells to its left —
so by the time we reach cell i the values we need are already final.
Climbing Stairs recurrence: To reach stair i you can come from stair i-1 (one step) or stair i-2 (two steps), so
Climbing Stairs recurrence: To reach stair i you can come from stair i-1 (one step) or stair i-2 (two steps), so
dp[i] = dp[i-1] + dp[i-2].
Computed
Current cell
Source cells (i-1, i-2)
Not yet computed
Controls
Time: O(n) | Space: O(n)
Steps
0 stepsPress Run to trace the algorithm one step at a time.