Dynamic Programming (DP)
Overlapping subproblems, optimal substructure, state definition, transition, base cases, evaluation order, answer extraction, and reconstruction of a solution.
Fundamentals
Overlapping subproblems, optimal substructure, state definition, transition, base cases, evaluation order, answer extraction, and reconstruction of a solution.
A DP solution answers four questions: what is the state (the smallest description of a subproblem), what is the transition (how a state's answer is built from smaller states), what are the base cases, and in what order can states be computed so dependencies are ready.
Beginner DP
Fibonacci, climbing stairs, min-cost stairs, frog jump, house robber, and grid paths.
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
#include <bits/stdc++.h>
using namespace std;
int main() {
// climbing stairs: ways(n) = ways(n-1) + ways(n-2)
vector<long long> ways(46); ways[0] = 1; ways[1] = 1;
for (int i = 2; i <= 45; ++i) ways[i] = ways[i - 1] + ways[i - 2];
cout << "ways to climb 10 stairs: " << ways[10] << ", 45 stairs: " << ways[45] << '\n';
// house robber: rob[i] = max(rob[i-1], rob[i-2] + v[i]); two variables suffice
vector<int> v = {2, 7, 9, 3, 1};
long long take = 0, skip = 0;
for (int x : v) { long long nt = skip + x; skip = max(skip, take); take = nt; }
cout << "house robber {2,7,9,3,1}: " << max(take, skip) << '\n';
// grid paths with obstacles
vector<string> g = {"....", ".#..", "...#", "#..."};
int R = 4, C = 4;
vector<vector<long long>> dp(R, vector<long long>(C, 0));
for (int r = 0; r < R; ++r) for (int c = 0; c < C; ++c) {
if (g[r][c] == '#') continue;
if (r == 0 && c == 0) { dp[r][c] = 1; continue; }
dp[r][c] = (r ? dp[r - 1][c] : 0) + (c ? dp[r][c - 1] : 0);
}
cout << "paths through the 4x4 grid avoiding #: " << dp[R - 1][C - 1] << '\n';
}ways to climb 10 stairs: 89, 45 stairs: 1836311903
house robber {2,7,9,3,1}: 12
paths through the 4x4 grid avoiding #: 3One-dimensional and sequence DP
Maximum subarray, longest increasing subsequence, longest divisible subset, maximum sum increasing subsequence, and partition problems.
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2): Python version of the O(n log n) LIS Output (CPython 3.13.1):
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> a = {10, 9, 2, 5, 3, 7, 101, 18, 4, 19};
int n = (int)a.size();
// O(n^2): len[i] = 1 + max len[j] over j < i with a[j] < a[i]; keep parents to reconstruct
vector<int> len(n, 1), parent(n, -1);
for (int i = 0; i < n; ++i) for (int j = 0; j < i; ++j) if (a[j] < a[i] && len[j] + 1 > len[i]) { len[i] = len[j] + 1; parent[i] = j; }
int end = int(max_element(len.begin(), len.end()) - len.begin());
vector<int> seq;
for (int i = end; i != -1; i = parent[i]) seq.push_back(a[i]);
reverse(seq.begin(), seq.end());
cout << "LIS length " << len[end] << ":";
for (int x : seq) cout << ' ' << x;
// O(n log n): tails[k] = smallest possible tail of an increasing subsequence of length k+1
vector<int> tails;
for (int x : a) {
auto it = lower_bound(tails.begin(), tails.end(), x);
if (it == tails.end()) tails.push_back(x); else *it = x;
}
cout << "\nO(n log n) length: " << tails.size() << " (tails array:";
for (int x : tails) cout << ' ' << x;
cout << " - not itself a subsequence)\n";
}LIS length 5: 2 5 7 18 19
O(n log n) length: 5 (tails array: 2 3 4 18 19 - not itself a subsequence)from bisect import bisect_left
def lis_length(a):
tails = [] # tails[k] = smallest tail of an increasing subsequence of length k+1
for x in a:
i = bisect_left(tails, x)
if i == len(tails):
tails.append(x)
else:
tails[i] = x
return len(tails)
print(lis_length([10, 9, 2, 5, 3, 7, 101, 18, 4, 19]))Knapsack family
0/1 knapsack, unbounded knapsack, subset sum, equal partition, target sum, coin change (minimum coins and number of ways), rod cutting, and bounded-knapsack concepts.
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
The loop direction is the whole difference between 0/1 and unbounded knapsack in one-dimensional form: iterating capacity downward means best[c − w] still holds the value from *before* this item was considered. Likewise, for coin change the loop order decides whether 1+2 and 2+1 count once (combinations) or twice (ordered sequences).
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> w = {10, 20, 30}, val = {60, 100, 120};
int W = 50;
// 0/1 knapsack in O(W) space: iterate capacity downward so each item is used at most once
vector<int> best(W + 1, 0);
for (size_t i = 0; i < w.size(); ++i)
for (int c = W; c >= w[i]; --c) best[c] = max(best[c], best[c - w[i]] + val[i]);
cout << "0/1 knapsack, capacity 50: " << best[W] << '\n';
// unbounded: iterate upward so an item can be reused
vector<int> unb(W + 1, 0);
for (size_t i = 0; i < w.size(); ++i)
for (int c = w[i]; c <= W; ++c) unb[c] = max(unb[c], unb[c - w[i]] + val[i]);
cout << "unbounded knapsack, capacity 50: " << unb[W] << '\n';
// coin change: minimum coins, and number of ways (combinations, order ignored)
vector<int> coins = {1, 2, 5}; int amount = 11;
vector<int> minCoins(amount + 1, INT_MAX); minCoins[0] = 0;
for (int x = 1; x <= amount; ++x) for (int c : coins) if (c <= x && minCoins[x - c] != INT_MAX) minCoins[x] = min(minCoins[x], minCoins[x - c] + 1);
vector<long long> combos(amount + 1, 0); combos[0] = 1;
for (int c : coins) for (int x = c; x <= amoun
…0/1 knapsack, capacity 50: 220
unbounded knapsack, capacity 50: 300
amount 11 with {1,2,5}: min coins 3, combinations 11, ordered sequences 218
{1,5,11,5} splits into two equal halves: trueString DP
Longest common subsequence, longest common substring, edit distance, shortest common supersequence, distinct subsequences, wildcard matching, and regular-expression matching overview.
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
Edit distance's three moves are delete (E[i−1][j] + 1), insert (E[i][j−1] + 1) and replace-or-match (E[i−1][j−1] + [s[i]≠t[j]]). The printed table is the dry run: the bottom-right cell is the answer, 3 (k→s, e→i, insert g).
#include <bits/stdc++.h>
using namespace std;
int main() {
string a = "AGGTAB", b = "GXTXAYB";
int n = (int)a.size(), m = (int)b.size();
vector<vector<int>> L(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j)
L[i][j] = a[i - 1] == b[j - 1] ? L[i - 1][j - 1] + 1 : max(L[i - 1][j], L[i][j - 1]);
string lcs;
for (int i = n, j = m; i > 0 && j > 0;) { // walk back through the table
if (a[i - 1] == b[j - 1]) { lcs += a[i - 1]; --i; --j; }
else if (L[i - 1][j] >= L[i][j - 1]) --i; else --j;
}
reverse(lcs.begin(), lcs.end());
cout << "LCS(" << a << ", " << b << ") = " << lcs << " (length " << L[n][m] << ")\n";
string s = "kitten", t = "sitting";
vector<vector<int>> E(s.size() + 1, vector<int>(t.size() + 1));
for (size_t i = 0; i <= s.size(); ++i) E[i][0] = (int)i;
for (size_t j = 0; j <= t.size(); ++j) E[0][j] = (int)j;
for (size_t i = 1; i <= s.size(); ++i) for (size_t j = 1; j <= t.size(); ++j)
E[i][j] = min({E[i - 1][j] + 1, E[i][j - 1] + 1, E[i - 1][j - 1] + (s[i - 1] != t[j - 1])});
cout << "edit distance(kitten, sitting) = " << E[s
…LCS(AGGTAB, GXTXAYB) = GTAB (length 4)
edit distance(kitten, sitting) = 3
s i t t i n g
0 1 2 3 4 5 6 7
k 1 1 2 3 4 5 6 7
i 2 2 1 2 3 4 5 6
t 3 3 2 1 2 3 4 5
t 4 4 3 2 1 2 3 4
e 5 5 4 3 2 2 3 4
n 6 6 5 4 3 3 2 3Grid and interval DP
Unique paths with obstacles, minimum path sum, triangle path, matrix-chain multiplication, burst balloons, palindrome partitioning, and interval merge costs.
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
Interval DP iterates by interval length, so every shorter interval it depends on is already computed.
#include <bits/stdc++.h>
using namespace std;
int main() {
// matrix-chain multiplication: dims p0 x p1, p1 x p2, ...; cost[i][j] = min over split k
vector<long long> p = {40, 20, 30, 10, 30};
int n = (int)p.size() - 1;
vector<vector<long long>> cost(n, vector<long long>(n, 0));
vector<vector<int>> split(n, vector<int>(n, 0));
for (int len = 2; len <= n; ++len) // shorter intervals first
for (int i = 0; i + len - 1 < n; ++i) {
int j = i + len - 1; cost[i][j] = LLONG_MAX;
for (int k = i; k < j; ++k) {
long long c = cost[i][k] + cost[k + 1][j] + p[i] * p[k + 1] * p[j + 1];
if (c < cost[i][j]) { cost[i][j] = c; split[i][j] = k; }
}
}
function<string(int, int)> paren = [&](int i, int j) -> string {
return i == j ? string(1, char('A' + i)) : "(" + paren(i, split[i][j]) + paren(split[i][j] + 1, j) + ")";
};
cout << "matrix chain 40x20, 20x30, 30x10, 10x30: " << cost[0][n - 1] << " multiplications, order " << paren(0, n - 1) << '\n';
// minimum path sum in a grid moving right/down
vector<vector<int>> g = {{1, 3, 1}, {1,
…matrix chain 40x20, 20x30, 30x10, 10x30: 26000 multiplications, order ((A(BC))D)
minimum path sum: 7Tree and graph DP
Tree diameter, subtree DP, maximum path sum, independent set on trees, DAG path counts, and rerooting DP.
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
#include <bits/stdc++.h>
using namespace std;
int main() {
// maximum-weight independent set on a tree: no two chosen nodes adjacent
int n = 7;
vector<vector<int>> adj(n);
vector<pair<int, int>> edges = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5}, {2, 6}};
for (auto [a, b] : edges) { adj[a].push_back(b); adj[b].push_back(a); }
vector<long long> w = {3, 2, 1, 10, 1, 1, 5};
vector<array<long long, 2>> dp(n); // dp[v][0]: v excluded, dp[v][1]: v included
function<void(int, int)> dfs = [&](int v, int parent) {
dp[v] = {0, w[v]};
for (int c : adj[v]) if (c != parent) {
dfs(c, v);
dp[v][0] += max(dp[c][0], dp[c][1]);
dp[v][1] += dp[c][0];
}
};
dfs(0, -1);
cout << "max independent set weight: " << max(dp[0][0], dp[0][1]) << '\n';
long long brute = 0;
for (int mask = 0; mask < 1 << n; ++mask) {
bool ok = true; long long s = 0;
for (auto [a, b] : edges) if ((mask >> a & 1) && (mask >> b & 1)) ok = false;
for (int v = 0; v < n; ++v) if (mask >> v & 1) s += w[v];
if (ok) brute = max(brute, s);
}
cout << "brute force over
…max independent set weight: 20
brute force over all 2^7 subsets: 20Bitmask DP
Traveling Salesperson Problem, assignment problem, and subset-state transitions. Explain O(n 2^n) memory/time constraints and bit-width limits.
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
The table has 2ⁿ·n states with n transitions each — O(n²·2ⁿ) time — compared with (n−1)! tours. That is practical up to about n = 20, and the mask must fit in the integer type.
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<vector<int>> d = {{0, 10, 15, 20}, {10, 0, 35, 25}, {15, 35, 0, 30}, {20, 25, 30, 0}};
int n = 4, FULL = 1 << n;
const int INF = 1e9;
// dp[mask][v]: shortest path starting at 0, visiting exactly the cities in mask, ending at v
vector<vector<int>> dp(FULL, vector<int>(n, INF));
dp[1][0] = 0;
for (int mask = 1; mask < FULL; ++mask)
for (int v = 0; v < n; ++v) {
if (!(mask >> v & 1) || dp[mask][v] == INF) continue;
for (int u = 0; u < n; ++u) if (!(mask >> u & 1))
dp[mask | 1 << u][u] = min(dp[mask | 1 << u][u], dp[mask][v] + d[v][u]);
}
int best = INF;
for (int v = 1; v < n; ++v) best = min(best, dp[FULL - 1][v] + d[v][0]);
cout << "shortest tour: " << best << '\n';
vector<int> perm = {1, 2, 3}; int brute = INF;
do { int c = d[0][perm[0]] + d[perm[0]][perm[1]] + d[perm[1]][perm[2]] + d[perm[2]][0]; brute = min(brute, c); } while (next_permutation(perm.begin(), perm.end()));
cout << "all " << 6 << " permutations: " << brute << '\n';
cout << "states for n = 20: " << (1 << 20) * 20 << " (fine); n = 30: about 3
…shortest tour: 80
all 6 permutations: 80
states for n = 20: 20971520 (fine); n = 30: about 3.2e10 (too many)Advanced DP optimization
Prefix/suffix optimization.
Monotonic queue optimization.
Convex hull trick / Li Chao tree.
SOS DP (sum over subsets).
DP on trees and rerooting.
DP with bitsets.
Teach required preconditions for each optimization; never apply an optimization solely because a recurrence "looks similar." Module 53 states each precondition and shows the techniques.
Practice
Easy: min-cost climbing stairs.
Medium: longest palindromic subsequence (LCS of a string and its reverse, or interval DP).
Hard: burst balloons (interval DP choosing the *last* balloon to burst in each interval).
Quiz
? In one-dimensional 0/1 knapsack, why iterate the capacity downward?
+ So `best[c − w]` still holds the value from before this item — each item is used at most once. :: Upward iteration gives the unbounded version.
- It is faster. :: Same complexity.
- To handle negative weights. :: Weights are non-negative.
- It does not matter. :: It decides 0/1 versus unbounded.
? Coin change with coins {1,2,5} and amount 11: the run printed 11 combinations but many more ordered sequences. Which loop order counts combinations?
+ Coins in the outer loop, amounts in the inner loop :: Each coin type is added in a fixed order, so 1+2 and 2+1 are the same.
- Amounts in the outer loop :: That counts ordered sequences.
- Either order :: The orders give different answers.
- Neither :: One of them does.
? Which is a correct statement of the O(n log n) LIS `tails` array?
+ tails[k] is the smallest tail of any increasing subsequence of length k+1, so its size is the LIS length. :: The array itself need not be a valid subsequence.
- tails is the longest increasing subsequence. :: The run printed `2 3 4 18 19` — 4 comes after 18 in the input, so it is not a subsequence.
- tails is sorted descending. :: It
…