If a problem has overlapping subproblems — you solve the same smaller problem multiple times — and optimal substructure — the best solution builds from best sub-solutions — cache the results. That's DP.
Here's the fib(5) call tree. Dashed nodes are redundant — the same subproblem solved again. The tree grows exponentially because we keep redoing work.
Remember how memoization pruned the tree? DP is just doing that systematically. Instead of recursing and caching, fill a table from the base cases up.
Bottom-up Fibonacci table
Build the table from the bottom up. No recursion needed.
How many ways can you reach the bottom-right corner of a grid, moving only right or down? Each cell's count is the sum of the cell above and the cell to the left. Watch the grid fill in diagonal waves.
Find unique paths from top-left to bottom-right in a 4×4 grid. Only move right or down.
Top-down
Recursion + cache. Start with the big problem, recurse into subproblems, cache results so you never recompute.
Bottom-up
Loop + table. Start with the smallest subproblems and build up to the answer iteratively. No recursion overhead.
Top-down = recursion + cache. Bottom-up = loop + table. Same idea, different direction. Bottom-up avoids stack depth limits and often runs faster in practice.
You can climb 1 or 2 steps at a time. How many distinct ways to reach step n? Each step's count = the two steps below it. Same recurrence as Fibonacci.
Top-down (memoized recursion)
function solve(n, memo = new Map()) { if (memo.has(n)) return memo.get(n) if (n <= 1) return n const result = solve(n - 1, memo) + solve(n - 2, memo) memo.set(n, result) return result }
Bottom-up (table iteration)
function solve(n) { const dp = [base0, base1] for (let i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2] } return dp[n] }
Climbing Stairs (concrete example)
function climbStairs(n) { if (n <= 2) return n let prev2 = 1, prev1 = 2 for (let i = 3; i <= n; i++) { const curr = prev1 + prev2 prev2 = prev1 prev1 = curr } return prev1 }
O(n²) or O(n*m) time — polynomial, not exponential