Loading...
Master memoization, tabulation, and advanced DP patterns
Section 0 of 0
Master memoization, tabulation, and advanced DP patterns
Dynamic Programming (DP) is an optimization technique used to solve complex problems by breaking them down into simpler, overlapping subproblems. It's the art of "smart memoization"—solving each unique piece only once.
A problem has optimal substructure if an optimal solution to the entire problem contains within it optimal solutions to its subproblems.
A recursive solution to the problem visits the same subproblems over and over again. Instead of re-computing, we solve it once and cache it.
Think of simple Recursion as a explorer who gets lost in a maze and keeps walking down the same dead ends repeatedly because they forgot they already went there.
"Dynamic Programming is basically taking notes while exploring the maze. If you find a dead end, write it down. If you find a path to the exit from a specific room, write it down! Next time you enter that room, just check your notes."
Without DP, the Fibonacci sequence $F(n) = F(n-1) + F(n-2)$ takes Exponential Time $O(2^n)$. With DP, it takes Linear Time $O(n)$. That is the difference between a calculation taking 100 years vs. 0.001 seconds for $n=100$.
"I will solve this by calling myself twice... even if I've done it already."
"Before calculating, I'll check my notebook (memo table). If it's there, I'm done."
1function fib(n, memo):2 if n <= 1: return n3 if memo[n] != null: 4 return memo[n] // Notebook Check!5 6 memo[n] = fib(n-1, memo) + fib(n-2, memo)7 return memo[n]DP often works by filling a grid (table). Each cell represents a "State". Observe how this table builds up to find the Longest Common Subsequence between two strings.
| B | D | C | A | B | A | ||
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| A | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| B | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| C | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| B | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| D | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| B | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Notice how each cell $(i, j)$ only depends on its neighbors: diagonal $(i-1, j-1)$, top $(i-1, j)$, or left $(i, j-1)$. This dependency determines the Loop Order.
What does dp[i] represent? Be precise (e.g., 'the max profit using items 1 to i').
How do you calculate dp[i] using previous states like dp[i-1]?
Define the simplest version (e.g., dp[0] = 0).
Choose Top-Down (Memoization) or Bottom-Up (Tabulation).
Do you really need the whole table? Can you use just two rows?
Next lesson: Strategies for Optimization.