DataslopeDynamic Programming
Learn memoization, tabulation, and classic dynamic programming patterns in C++
Dynamic programming solves problems by combining answers to overlapping subproblems with optimal substructure. It is the next step after recursion: the Fibonacci tree in recursion.mdx repeats calls; DP stores those answers.
Mindset
Top-down memoization is recursion plus a cache. Bottom-up tabulation fills a table from base cases upward.
Define the state first
Before coding, say exactly what dp[i] or dp[i][j] means. The transition usually follows naturally.
Fibonacci
Naive recursion is exponential because it repeats work.
Climbing stairs
If you may climb 1 or 2 steps, f(n) = f(n-1) + f(n-2) because the last move comes from one of those states.
Coin change: min coins
Let dp[a] be the minimum coins for amount a; try each coin as the last coin.
0/1 knapsack
dp[i][w] is the best value using the first i items and capacity w.
| item | weight | value |
|---|---|---|
| 0 | 2 | 12 |
| 1 | 1 | 10 |
| 2 | 3 | 20 |
| 3 | 2 | 15 |
LCS and LIS
For LCS, dp[i][j] is the best length for prefixes a[0..i) and b[0..j). Example ABCBDAB / BDCABC has length 4.
For LIS, dp[i] is the longest increasing subsequence ending at i. The O(n log n) patience-sort version is faster, but O(n²) is the clearest DP.
Identifying and optimizing DP
Use DP when you see optimal substructure and overlapping subproblems. Optimize space with rolling arrays when a row only depends on previous rows.
Implement int climbStairs(int n) for n=1..45. The driver prints several values.
Implement int coinChange(std::vector<int> coins, int amount). Return -1 if impossible.
Implement int knapsack(int W, const std::vector<int>& weights, const std::vector<int>& values).
Check your understanding
When does DP apply best?
Every subproblem is unique.
The problem has optimal substructure and overlapping subproblems.
The input is always sorted.
Only for graphs.
What is top-down DP?
Recursion plus a cache.
Iteration without storage.
Sorting by value.
A binary search tree.
The standard LCS table for lengths n and m costs:
O(n + m)
O(nm)
O(log n)
O(2^n)
Why can Fibonacci use O(1) extra space?
It has no base case.
C++ memoizes automatically.
Each state needs only the previous two values.
It only works for n=10.