Dynamic Programming I: Patterns
A five-step method for dynamic programming and the patterns it produces, from coin change and knapsack to LIS, LCS, edit distance and grid paths, each checked against a brute force.
The same subproblem, millions of times
A trail runner passes n checkpoints in a row. Checkpoint i offers a snack worth v[i] points, but after taking a snack the runner needs the next checkpoint to digest, so no two adjacent snacks can both be taken. What is the most a runner can collect?
The honest first attempt is a recursion. At checkpoint i, either skip it and continue from i + 1, or take it and continue from i + 2. That is correct, and on 30 checkpoints it makes over four million calls, because "the best from checkpoint 7 on" is computed again for every way of reaching checkpoint 7. There are only 30 different questions. The recursion asks them millions of times.
Dynamic programming (DP) is the discipline of asking each question once: name the subproblems, store their answers, and compute them in an order where every answer you need is already there. Done right, the snack problem takes 30 steps. Done slightly wrong (one loop running the wrong way, one missing marker for "impossible") it gives wrong answers that look plausible, which is why every pattern in this lesson comes with a brute-force stress test in the style of Fast I/O, Contest Templates and Stress Testing. You met one DP already: Floyd-Warshall in Shortest Paths is a DP over the set of allowed intermediate vertices.
A five-step method
Every DP in this lesson, and in Dynamic Programming II, is written the same way. Write the five answers down, in words, before you write code.
- State. What does one table entry mean, in a full sentence? For the snack problem:
best[i]is the most points collectable from checkpointsi..n-1. - Transition. How is an entry computed from smaller ones?
best[i] = max(best[i + 1], v[i] + best[i + 2]): skipi, or take it and skipi + 1. - Order. In which order must entries be computed so that the ones on the right-hand side are ready?
best[i]needsi + 1andi + 2, soiruns downwards. - Base cases. Which entries have no smaller subproblem? Past the end there is nothing to collect:
best[n] = best[n + 1] = 0. - Answer. Which entry, or which combination, answers the question?
best[0].
The state is the hard part, and the test for a good one is the sentence in step 1: it must contain everything the future depends on and nothing else. "Most points from checkpoint i on" is enough because what happens after i does not depend on how the runner got there; the transition already handles the one constraint (no adjacent snacks) by jumping to i + 2. Counting stairs climbed one or two at a time is the same shape: ways[i] = ways[i - 1] + ways[i - 2].
The cost of a DP is the number of states times the work per transition: here n states, O(1) each, so O(n).
Top-down or bottom-up
There are two ways to turn the method into code. Top-down (memoization) keeps the recursion and adds a cache: before computing best(i), look it up; after computing it, store it. Bottom-up (tabulation) fills an array in the order from step 3 with a loop. This program shows the naive recursion, the memoized one and the table, counts calls for growing n, and checks both fast versions against a brute force that tries every subset of checkpoints with no two neighbors.
#include <algorithm>
#include <cstdint>
#include <print>
#include <vector>
using ll = long long;
struct Lcg {
std::uint64_t s;
std::uint32_t next() {
s = s * 6364136223846793005ULL + 1442695040888963407ULL;
return std::uint32_t(s >> 33);
}
int range(int lo, int hi) { return lo + int(next() % std::uint32_t(hi - lo + 1)); }
};
long calls = 0;
// best(i): the most snack value from checkpoints i..n-1, never taking two neighbors.
ll naive(const std::vector<ll>& v, int i) {
++calls;
if (i >= int(v.size())) return 0;
return std::max(naive(v, i + 1), v[i] + naive(v, i + 2)); // skip i, or take it
}
ll memo(const std::vector<ll>& v, int i, std::vector<ll>& seen) {
++calls;
if (i >= int(v.size())) return 0;
if (seen[i] != -1) return seen[i]; // -1: not computed yet (answers are >= 0)
return seen[i] = std::max(memo(v, i + 1, seen), v[i] + memo(v, i + 2, seen));
}
ll table(const std::vector<ll>& v) {
int n = int(v.size());
std::vector<ll> best(n + 2, 0); // base cases: best[n] = best[n+1] = 0
for (int i = n - 1; i >= 0; --i) // i needs i+1 and i+2: go downwards
best[i] = std::max(best[i + 1], v[i] + best[i + 2]);
return best[0];
}
ll brute(const std::vector<ll>& v) { // every subset without two neighbors
int n = int(v.size());
ll answer = 0;
for (std::uint32_t mask = 0; mask < (1u << n); ++mask) {
if (mask & (mask >> 1)) continue;
ll sum = 0;
for (int i = 0; i < n; ++i) if (mask >> i & 1) sum += v[i];
answer = std::max(answer, sum);
}
return answer;
}
int main() {
std::vector<ll> sample{4, 9, 6, 2, 7, 3, 8};
std::println("sample: {}", table(sample));
std::println("{:>3} {:>12} {:>8}", "n", "naive calls", "memo calls");
for (int n = 10; n <= 30; n += 10) {
std::vector<ll> v(n, 1);
calls = 0;
naive(v, 0);
long naiveCalls = calls;
std::vector<ll> seen(n, -1);
calls = 0;
memo(v, 0, seen);
std::println("{:>3} {:>12} {:>8}", n, naiveCalls, calls);
}
Lcg rng{6};
int failures = 0;
for (int t = 0; t < 2000; ++t) {
std::vector<ll> v(rng.range(0, 12));
for (ll& x : v) x = rng.range(0, 20);
std::vector<ll> seen(v.size(), -1);
ll want = brute(v);
failures += table(v) != want || memo(v, 0, seen) != want;
}
std::println("2000 random inputs, disagreements: {}", failures);
}Press Run to compile and run this example.
sample: 25
n naive calls memo calls
10 287 21
20 35421 41
30 4356617 61
2000 random inputs, disagreements: 0The sample 4 9 6 2 7 3 8 gives 25, from checkpoints 0, 2, 4 and 6 (4 + 6 + 7 + 8), not the tempting 9 + 7 + 8 = 24. The naive call count grows by a factor of about 123 for every 10 extra checkpoints, which is roughly the golden ratio to the 10th power, the growth rate of the Fibonacci numbers. Memoization makes it 2n + 1 calls.
Which to use:
- Top-down is easier when only some states are reachable, or when the order is awkward to work out: the recursion finds the order for you. Its costs are function-call overhead and recursion depth: a memoized recursion over
10^6states is10^6frames deep, which can overflow the stack on a judge. - Bottom-up has no recursion, makes the memory layout obvious, and is the only one of the two that allows keeping just the last row or two of the table, as the knapsack below does.
In the memo, -1 means "not computed yet". That works only because every real answer is at least 0. Choosing that marker is a decision, and the pitfalls come back to it.
Coin change: fewest, combinations, permutations
A post office sells stamps in a few values. For a parcel that needs exactly x cents of postage, three different questions come up, and they need three different DPs.
- Fewest stamps. State
fewest[x]: the fewest stamps with total exactlyx. Transition: try each stampsas the last one,fewest[x] = min(fewest[x - s] + 1). Some amounts cannot be made at all, so "impossible" needs a value of its own; here it iskInf, and it is never used as a source. - Sets of stamps, where
3 + 5and5 + 3are the same set. Process stamp values in the outer loop and amounts in the inner loop. Each set is then built in one fixed order (all 3s, then all 5s, then all 7s), so it is counted once. - Rows of stamps, stuck on the parcel left to right, where
3 + 5and5 + 3are different. Process amounts in the outer loop and try every stamp as the last one in the inner loop. This counts ordered sequences.
The two counting versions have the same transition and differ only in loop order. Counts grow quickly, so they are reported modulo kMod = 1'000'000'007, as problems usually require; more on that with the grid below.
#include <algorithm>
#include <cstdint>
#include <limits>
#include <print>
#include <string>
#include <vector>
using ll = long long;
constexpr ll kInf = std::numeric_limits<ll>::max() / 4;
constexpr ll kMod = 1'000'000'007;
struct Lcg {
std::uint64_t s;
std::uint32_t next() {
s = s * 6364136223846793005ULL + 1442695040888963407ULL;
return std::uint32_t(s >> 33);
}
int range(int lo, int hi) { return lo + int(next() % std::uint32_t(hi - lo + 1)); }
};
struct Counts { std::vector<ll> fewest, sets, rows; };
Counts stampTables(const std::vector<int>& stamps, int target) {
Counts c{std::vector<ll>(target + 1, kInf), std::vector<ll>(target + 1, 0),
std::vector<ll>(target + 1, 0)};
c.fewest[0] = 0; // fewest[x]: fewest stamps for exactly x; kInf: impossible
for (int x = 1; x <= target; ++x)
for (int s : stamps)
if (s <= x && c.fewest[x - s] != kInf)
c.fewest[x] = std::min(c.fewest[x], c.fewest[x - s] + 1);
// Stamps outer, amounts inner: each multiset is built in one fixed order.
c.sets[0] = 1;
for (int s : stamps)
for (int x = s; x <= target; ++x) c.sets[x] = (c.sets[x] + c.sets[x - s]) % kMod;
// Amounts outer, stamps inner: the last stamp can be any kind, so order counts.
c.rows[0] = 1;
for (int x = 1; x <= target; ++x)
for (int s : stamps)
if (s <= x) c.rows[x] = (c.rows[x] + c.rows[x - s]) % kMod;
return c;
}
// Brute force: list every row of stamps that sums to x; a row with
// nondecreasing kinds stands for one multiset.
struct Tally { ll fewest = kInf, sets = 0, rows = 0; };
void rowsOf(const std::vector<int>& st, int x, int lastKind, bool sorted, int used,
Tally& t) {
if (x == 0) {
++t.rows;
t.sets += sorted;
t.fewest = std::min<ll>(t.fewest, used);
return;
}
for (int k = 0; k < int(st.size()); ++k)
if (st[k] <= x) rowsOf(st, x - st[k], k, sorted && k >= lastKind, used + 1, t);
}
int main() {
std::vector<int> stamps{3, 5, 7};
Counts c = stampTables(stamps, 12);
std::println("amount fewest sets rows");
for (int x = 1; x <= 12; ++x)
std::println("{:>6} {:>6} {:>4} {:>4}", x,
c.fewest[x] == kInf ? "-" : std::to_string(c.fewest[x]),
c.sets[x], c.rows[x]);
Lcg rng{8};
int checked = 0, failures = 0;
for (int t = 0; t < 300; ++t) {
std::vector<int> st(rng.range(1, 3));
for (int& s : st) s = rng.range(1, 6);
std::ranges::sort(st);
auto [last, end] = std::ranges::unique(st);
st.erase(last, end); // the problem lists distinct kinds
Counts fast = stampTables(st, 14);
for (int x = 0; x <= 14; ++x, ++checked) {
Tally t;
rowsOf(st, x, 0, true, 0, t);
failures += fast.fewest[x] != t.fewest || fast.sets[x] != t.sets ||
fast.rows[x] != t.rows;
}
}
std::println("{} (stamps, amount) pairs, disagreements: {}", checked, failures);
}Press Run to compile and run this example.
amount fewest sets rows
1 - 0 0
2 - 0 0
3 1 1 1
4 - 0 0
5 1 1 1
6 2 1 1
7 1 1 1
8 2 1 2
9 3 1 1
10 2 2 3
11 3 1 3
12 2 2 3
4500 (stamps, amount) pairs, disagreements: 0For 10 cents there are two sets (5 + 5 and 3 + 7) but three rows (5 5, 3 7, 7 3). Amounts 1, 2 and 4 are impossible with stamps 3, 5 and 7. All three tables cost O(k * x) for k stamp values. The brute force lists every row of stamps that sums to x and counts a row as a set only when its stamp kinds appear in nondecreasing order. To make sure it can fail, we swapped the loops of the sets table, which turns it into the rows table: it reported 1266 disagreements out of 4500.
0/1 knapsack: the loop direction is the algorithm
A hiker has a backpack that holds weight W and a list of items, each with a weight and a value, each available once. Maximize the total value that fits.
State: best[i][c] is the best value using only the first i items with total weight at most c. Transition: skip item i, or take it, best[i][c] = max(best[i - 1][c], best[i - 1][c - w] + v). Base cases: best[0][c] = 0. Answer: best[n][W]. That is O(n * W) time and memory.
Row i only reads row i - 1, so one row is enough if you are careful. Overwrite it in place with c running downwards: when you compute best[c], the entry best[c - w] still holds the old row's value, because c - w < c has not been overwritten yet. Run c upwards and best[c - w] may already include the current item, so the item can be taken again and again. That is no longer the 0/1 knapsack. It is the unbounded knapsack, where each item may be taken any number of times.
#include <algorithm>
#include <cstdint>
#include <print>
#include <vector>
using ll = long long;
struct Lcg {
std::uint64_t s;
std::uint32_t next() {
s = s * 6364136223846793005ULL + 1442695040888963407ULL;
return std::uint32_t(s >> 33);
}
int range(int lo, int hi) { return lo + int(next() % std::uint32_t(hi - lo + 1)); }
};
struct Item { int weight; ll value; };
// best[i][c]: best value from the first i items with total weight <= c.
ll table2d(const std::vector<Item>& items, int cap) {
int n = int(items.size());
std::vector best(n + 1, std::vector<ll>(cap + 1, 0));
for (int i = 1; i <= n; ++i) {
auto [w, v] = items[i - 1];
for (int c = 0; c <= cap; ++c) {
best[i][c] = best[i - 1][c]; // skip item
if (w <= c) best[i][c] = std::max(best[i][c], best[i - 1][c - w] + v);
}
}
return best[n][cap];
}
// One row, reused. Downwards, best[c - w] still holds the previous row's value.
ll rowDown(const std::vector<Item>& items, int cap) {
std::vector<ll> best(cap + 1, 0);
for (auto [w, v] : items)
for (int c = cap; c >= w; --c) best[c] = std::max(best[c], best[c - w] + v);
return best[cap];
}
// The bug: upwards, best[c - w] may already include this item.
ll rowUp(const std::vector<Item>& items, int cap) {
std::vector<ll> best(cap + 1, 0);
for (auto [w, v] : items)
for (int c = w; c <= cap; ++c) best[c] = std::max(best[c], best[c - w] + v);
return best[cap];
}
ll bruteOnce(const std::vector<Item>& items, int cap) { // every subset
ll answer = 0;
for (std::uint32_t mask = 0; mask < (1u << items.size()); ++mask) {
ll w = 0, v = 0;
for (std::size_t i = 0; i < items.size(); ++i)
if (mask >> i & 1) w += items[i].weight, v += items[i].value;
if (w <= cap) answer = std::max(answer, v);
}
return answer;
}
// Any number of each item: every multiset, listed with item indexes nondecreasing.
ll bruteMany(const std::vector<Item>& items, int cap, std::size_t from = 0) {
ll answer = 0;
for (std::size_t i = from; i < items.size(); ++i)
if (items[i].weight <= cap)
answer = std::max(answer, items[i].value +
bruteMany(items, cap - items[i].weight, i));
return answer;
}
int main() {
std::vector<Item> sample{{5, 10}, {4, 7}, {3, 6}, {2, 3}};
std::println("capacity 10: 2d {}, row down {}, row up {}", table2d(sample, 10),
rowDown(sample, 10), rowUp(sample, 10));
Lcg rng{4};
int bad2d = 0, badDown = 0, upVsOnce = 0, upVsMany = 0;
for (int t = 0; t < 2000; ++t) {
std::vector<Item> items(rng.range(0, 6));
for (auto& [w, v] : items) w = rng.range(1, 6), v = rng.range(0, 9);
int cap = rng.range(0, 12);
ll once = bruteOnce(items, cap), many = bruteMany(items, cap);
bad2d += table2d(items, cap) != once;
badDown += rowDown(items, cap) != once;
upVsOnce += rowUp(items, cap) != once;
upVsMany += rowUp(items, cap) != many;
}
std::println("2000 random inputs, disagreements with the subset brute force:");
std::println(" 2d table {}, row down {}, row up {}", bad2d, badDown, upVsOnce);
std::println("row up against 'any number of each item': {}", upVsMany);
}Press Run to compile and run this example.
capacity 10: 2d 19, row down 19, row up 20
2000 random inputs, disagreements with the subset brute force:
2d table 0, row down 0, row up 1026
row up against 'any number of each item': 0On the sample with capacity 10, the upward loop finds 20 by packing the 5 kg, 10-point item twice; the true 0/1 answer is 19. The stress test makes the point exactly: the upward version disagrees with the subset brute force on about half the inputs and agrees with a brute force for "any number of each item" on all of them. So the upward loop is the correct code for the unbounded knapsack, and a bug for the 0/1 one. Coin change above is an unbounded problem, which is why its loops run upwards.
O(n * W) is called pseudo-polynomial: it is polynomial in the value W, not in the length of the input. With n = 100 and W = 10^5 it is 10^7 steps; with W = 10^9 the table does not fit in memory, and you need a different state (for example, the least weight for each total value, if values are small).
Reconstructing the choice, not just the value
Problems often ask for the items, the path or the string, not only the number. The standard technique: keep the full table, start at the answer entry, and at each step ask which transition produced the stored value. For the knapsack, if best[i][c] == best[i - 1][c], skipping item i explains the value; otherwise item i was taken and the walk continues at best[i - 1][c - w].
6 12 n W; then n lines "name weight value"
stove 4 9
tent 7 13
rope 2 3
lamp 1 2
filter 3 6
jacket 5 8#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
using ll = long long;
struct Item { std::string name; int weight; ll value; };
void solve(std::istream& in, std::ostream& out) {
int n, cap;
in >> n >> cap;
std::vector<Item> items(n);
for (auto& [name, w, v] : items) in >> name >> w >> v;
// Keep the whole table: reconstruction needs every row, not just the last.
std::vector best(n + 1, std::vector<ll>(cap + 1, 0));
for (int i = 1; i <= n; ++i)
for (int c = 0; c <= cap; ++c) {
best[i][c] = best[i - 1][c];
int w = items[i - 1].weight;
ll v = items[i - 1].value;
if (w <= c) best[i][c] = std::max(best[i][c], best[i - 1][c - w] + v);
}
// Walk back from the answer: if skipping item i explains best[i][c], skip it.
std::vector<std::string> packed;
int c = cap;
for (int i = n; i >= 1; --i) {
if (best[i][c] == best[i - 1][c]) continue;
packed.push_back(items[i - 1].name);
c -= items[i - 1].weight;
}
std::ranges::reverse(packed);
out << "value " << best[n][cap] << ", weight " << cap - c << ", packed:";
for (const auto& name : packed) out << ' ' << name;
out << '\n';
}
int main() {
std::istringstream in(R"(6 12
stove 4 9
tent 7 13
rope 2 3
lamp 1 2
filter 3 6
jacket 5 8
)");
solve(in, std::cout); // on a judge: solve(std::cin, std::cout)
}Press Run to compile and run this example.
value 24, weight 12, packed: stove tent lampReconstruction is the reason not to compress the table too early. The one-row version computes the same value 24, but it has thrown away the rows that the walk back needs. If memory forbids the full table, store one bit per state ("taken or not") instead of the values: 64 times less memory than a table of long long, and still enough to walk back. When several choices give the same value, the walk returns one of them; which one depends on the order of the checks, so if a problem asks for a specific one (the lexicographically smallest, for example) the order must be designed for it.
Longest increasing subsequence in two complexities
Daily temperatures are recorded for n days. Find the longest run of days, not necessarily consecutive, on which the temperature strictly rises, and print it. This is the longest increasing subsequence (LIS).
The direct DP: len[i] is the length of the longest strictly increasing subsequence that ends at day i, and len[i] = 1 + max(len[j]) over earlier days j with a[j] < a[i]. That is O(n^2). The faster method keeps, for every length k, the smallest possible last value of an increasing subsequence of length k + 1, in an array tail. This array is always strictly increasing, so for each new value a binary search finds the first entry >= a[i] and replaces it (or appends if there is none). Each step is O(log n), so the whole is O(n log n). Storing indices in tail and a predecessor link prev[i] for each element lets you rebuild one actual subsequence.
#include <algorithm>
#include <cstdint>
#include <functional>
#include <print>
#include <vector>
struct Lcg {
std::uint64_t s;
std::uint32_t next() {
s = s * 6364136223846793005ULL + 1442695040888963407ULL;
return std::uint32_t(s >> 33);
}
int range(int lo, int hi) { return lo + int(next() % std::uint32_t(hi - lo + 1)); }
};
long steps = 0;
// O(n^2): len[i] = longest strictly increasing subsequence ending at a[i].
int lisQuadratic(const std::vector<int>& a) {
std::vector<int> len(a.size(), 1);
for (std::size_t i = 0; i < a.size(); ++i)
for (std::size_t j = 0; j < i; ++j, ++steps)
if (a[j] < a[i]) len[i] = std::max(len[i], len[j] + 1);
return a.empty() ? 0 : std::ranges::max(len);
}
// O(n log n): tail[k] = index of the smallest last value of an increasing
// subsequence of length k + 1. prev[] links each element to its predecessor.
std::vector<int> lisFast(const std::vector<int>& a) {
std::vector<int> tail, prev(a.size(), -1);
for (int i = 0; i < int(a.size()); ++i) {
auto it = std::ranges::lower_bound(tail, a[i], [](int x, int y) {
++steps;
return x < y;
}, [&](int idx) { return a[idx]; }); // first tail >= a[i]: strict increase
if (it != tail.begin()) prev[i] = *(it - 1);
if (it == tail.end()) tail.push_back(i);
else *it = i;
}
std::vector<int> seq;
for (int i = tail.empty() ? -1 : tail.back(); i != -1; i = prev[i])
seq.push_back(a[i]);
std::ranges::reverse(seq);
return seq;
}
int brute(const std::vector<int>& a) { // every subset, kept if strictly increasing
int best = 0, n = int(a.size());
for (std::uint32_t mask = 0; mask < (1u << n); ++mask) {
int last = -1, len = 0;
bool ok = true;
for (int i = 0; i < n && ok; ++i)
if (mask >> i & 1) ok = a[i] > last, last = a[i], ++len;
if (ok) best = std::max(best, len);
}
return best;
}
bool isSubsequence(const std::vector<int>& s, const std::vector<int>& a) {
std::size_t k = 0;
for (int x : a) if (k < s.size() && s[k] == x) ++k;
return k == s.size();
}
int main() {
std::vector<int> temps{12, 15, 11, 13, 13, 18, 14, 16, 20, 17};
auto seq = lisFast(temps);
std::print("length {}:", seq.size());
for (int x : seq) std::print(" {}", x);
std::println("");
Lcg rng{12};
std::println("{:>5} {:>10} {:>9}", "n", "quadratic", "n log n");
for (int n = 1000; n <= 8000; n *= 2) {
std::vector<int> a(n);
for (int& x : a) x = rng.range(0, 1'000'000);
steps = 0;
lisQuadratic(a);
long quadratic = steps;
steps = 0;
lisFast(a);
std::println("{:>5} {:>10} {:>9}", n, quadratic, steps);
}
int failures = 0;
for (int t = 0; t < 2000; ++t) {
std::vector<int> a(rng.range(0, 12));
for (int& x : a) x = rng.range(0, 5); // small values: many repeats
int want = brute(a);
auto s = lisFast(a);
bool valid = isSubsequence(s, a) &&
std::ranges::adjacent_find(s, std::greater_equal<>{}) == s.end();
failures += lisQuadratic(a) != want || int(s.size()) != want || !valid;
}
std::println("2000 random inputs, disagreements: {}", failures);
}Press Run to compile and run this example.
length 5: 11 13 14 16 17
n quadratic n log n
1000 499500 5198
2000 1999000 11328
4000 7998000 24938
8000 31996000 54009
2000 random inputs, disagreements: 0The quadratic version performs exactly n(n - 1) / 2 inner iterations; the binary-search version grows a little faster than linearly. At n = 8000 that is 32 million against 54 thousand; at n = 2*10^5 the first would need 2*10^10 and is out of the question. The temperature sample has several longest subsequences of length 5 (12 13 14 16 20 is another); the program prints the one that its predecessor links lead to.
The strictness is decided by one comparison. lower_bound (first element >= x) gives a strictly increasing subsequence; upper_bound (first element > x) gives a nondecreasing one. When we changed the comparator from < to <=, which turns lower_bound into upper_bound, the stress test, whose values repeat often, reported 1291 disagreements. Read the statement for "increasing" versus "non-decreasing" and test with repeated values.