Dynamic programming II

Dynamic programming I was about one-dimensional states: an amount, an index, a capacity. The recipe doesn't change — name the state in words, write the recurrence, fix the base cases, pick an order where every state's inputs are ready, then shrink the memory if you can — but the states get richer:

State shape	Example	Order that works
two prefixes `(i, j)`	edit distance, LCS	rows, then columns
an interval `[i, j]`	matrix chain, burst balloons	by interval length
a subset (bitmask) + extra	TSP, assignment	increasing mask
a subtree	independent set on a tree	children before parents
a vertex of a DAG	paths in a DAG	topological order
a digit position + "tight"	count x ≤ N with a property	most significant digit first

1. Two strings: edit distance

d[i][j] = fewest single-character edits turning the first i characters of a into the first j characters of b. Look at the last step of an optimal script:

the last characters are aligned: keep (free if equal) or replace (cost 1) → d[i−1][j−1] + (a[i−1] ≠ b[j−1])
a[i−1] was erased → d[i−1][j] + 1
b[j−1] was inserted → d[i][j−1] + 1

Base cases: d[i][0] = i (erase everything), d[0][j] = j (insert everything). To get the script, not just the number, keep the whole table and walk back from (n, m), at each cell choosing a term that produced its value:

Edit distance, kitten → sitting

start / 2

d[i][j] = edits turning the first i letters of kitten into the first j of sitting. Each cell reads three neighbours; step through to walk back the optimal script from the corner.

C++

#include <algorithm>
#include <format>
#include <print>
#include <string>
#include <string_view>
#include <vector>

int main() {
    std::string_view a = "kitten", b = "sitting";
    const std::size_t n = a.size(), m = b.size();
    std::vector<std::vector<std::size_t>> d(n + 1, std::vector<std::size_t>(m + 1));
    for (std::size_t i = 0; i <= n; ++i) d[i][0] = i;
    for (std::size_t j = 0; j <= m; ++j) d[0][j] = j;
    for (std::size_t i = 1; i <= n; ++i)
        for (std::size_t j = 1; j <= m; ++j)
            d[i][j] = std::min({d[i - 1][j - 1] + (a[i - 1] == b[j - 1] ? 0u : 1u),
                                d[i - 1][j] + 1, d[i][j - 1] + 1});

    // Walk back from the corner; steps come out reversed.
    std::vector<std::string> steps;
    std::size_t i = n, j = m;
    while (i > 0 || j > 0) {
        if (i > 0 && j > 0 && d[i][j] == d[i - 1][j - 1] + (a[i - 1] == b[j - 1] ? 0u : 1u)) {
            steps.push_back(a[i - 1] == b[j - 1] ? std::format("keep {}", a[i - 1])
                                                 : std::format("replace {} with {}", a[i - 1], b[j - 1]));
            --i, --j;
        } else if (i > 0 && d[i][j] == d[i - 1][j] + 1) {
            steps.push_back(std::format("erase {}", a[i - 1]));
            --i;
        } else {
            steps.push_back(std::format("insert {}", b[j - 1]));
            --j;
        }
    }
    std::ranges::reverse(steps);
    std::println("distance {}", d[n][m]);
    for (const auto& s : steps) std::println("  {}", s);
}

When several terms tie, any of them gives an optimal script — the distance is unique, the script isn't.

Only the value? One row is enough

LCS (longest common subsequence) has the same shape with max instead of min: t[i][j] = t[i−1][j−1] + 1 on a match, else max(t[i−1][j], t[i][j−1]). Each row reads only the row above it, so if you need just the length, keep one row over the shorter string — O(min(n, m)) memory instead of O(n·m). The trap: on a match you need the previous row's j − 1, which a single row has already overwritten. Save it first:

C++

std::size_t diag = 0;                 // previous row, column j - 1
for (std::size_t j = 1; j <= m; ++j) {
    std::size_t up = row[j];          // previous row, column j — next column's diag
    row[j] = (x == b[j - 1]) ? diag + 1 : std::max(row[j], row[j - 1]);
    diag = up;
}

Rolling arrays give up the table you'd walk back through. If you need the subsequence itself in linear memory, Hirschberg's algorithm splits a in the middle, finds where an optimal alignment crosses that row (one forward and one backward rolling pass), and recurses on the two halves — O(n·m) time, O(n + m) memory.

2. Intervals: order by length

Some problems are about contiguous ranges: the cheapest way to multiply a chain of matrices, to merge piles, to burst balloons. The state is an interval [i, j] and the recurrence tries every split point k:

cost[i][j] = min over k of cost[i][k] + cost[k+1][j] + (price of combining)

cost[i][j] reads only shorter intervals, so fill by length:

C++

#include <algorithm>
#include <cstdint>
#include <limits>
#include <print>
#include <vector>

int main() {
    // Matrix i has dims[i] × dims[i+1]: 10×30, 30×5, 5×60.
    std::vector<std::int64_t> dims{10, 30, 5, 60};
    const std::size_t n = dims.size() - 1;
    std::vector<std::vector<std::int64_t>> cost(n, std::vector<std::int64_t>(n, 0));
    for (std::size_t len = 2; len <= n; ++len) {
        for (std::size_t i = 0; i + len <= n; ++i) {
            std::size_t j = i + len - 1;
            cost[i][j] = std::numeric_limits<std::int64_t>::max();
            for (std::size_t k = i; k < j; ++k)
                cost[i][j] = std::min(cost[i][j], cost[i][k] + cost[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1]);
        }
    }
    std::println("{}", cost[0][n - 1]);  // (AB)C: 10·30·5 + 10·5·60 = 4500
}

O(n²) intervals × O(n) splits = O(n³).

Interval DP fills by length: the diagonals, outwards

start / 2

Matrices 10×30, 30×5, 5×60. cost[i][j] reads only shorter intervals, so length-1 (the diagonal) comes first, then length 2, then the whole chain.

3. Subsets as bitmasks

When n is small (≈ 20) and the state must remember which elements are used, encode the set as the bits of an integer. Worked example — assign n workers to n jobs at minimum total cost. If mask is the set of jobs already taken, the next worker to assign is worker popcount(mask), so the state is just the mask:

C++

#include <algorithm>
#include <bit>
#include <cstdint>
#include <limits>
#include <print>
#include <vector>

int main() {
    std::vector<std::vector<std::int64_t>> cost{
        {9, 2, 7, 8},
        {6, 4, 3, 7},
        {5, 8, 1, 8},
        {7, 6, 9, 4},
    };
    const std::size_t n = cost.size();
    constexpr std::int64_t inf = std::numeric_limits<std::int64_t>::max();
    std::vector<std::int64_t> best(std::size_t{1} << n, inf);
    best[0] = 0;
    for (std::size_t mask = 0; mask < best.size(); ++mask) {
        if (best[mask] == inf) continue;
        std::size_t worker = static_cast<std::size_t>(std::popcount(mask));
        if (worker == n) continue;
        for (std::size_t job = 0; job < n; ++job)
            if (!(mask >> job & 1))
                best[mask | std::size_t{1} << job] =
                    std::min(best[mask | std::size_t{1} << job], best[mask] + cost[worker][job]);
    }
    std::println("{}", best.back());  // 2 + 6 + 1 + 4 = 13
}

Increasing mask order works because every transition adds a bit, so the new mask is always larger. 2ⁿ states × n transitions = O(2ⁿ·n).

The state is a set of taken jobs, stored as bits

mask = 0b0101: jobs 0 and 2 are taken, so the next worker is popcount(mask) = 2. Each transition sets one more bit, so the new mask is always larger.

Travelling salesman needs one more piece of state: it matters where you are standing. best[mask][v] = cheapest path from city 0 that visited exactly mask and ends at v. Transitions go to a city w ∉ mask; the answer closes the tour from each v back to 0. That's 2ⁿ·n states × n transitions — O(2ⁿ·n²), about 17 million steps for 16 cities, against 15! ≈ 1.3 trillion orders for brute force.

Build masks from an unsigned type that's wide enough — std::size_t{1} << n, not 1 << n — and skip unreachable states instead of adding to an "infinity" sentinel.

4. Subtrees: children before parents

On a tree, the state is "the best answer inside the subtree of u", often with a flag. Maximum-weight independent set (no two chosen vertices adjacent):

take[u] = w[u] + Σ skip[c] over children c — u chosen, children not
skip[u] = Σ max(take[c], skip[c]) — u not chosen, children free

Any order that finishes children before parents works. Recursion is the obvious one and fails on deep trees (a path of 200,000 vertices is 200,000 stack frames). Instead compute a BFS order with parents and walk it backwards:

Children before parents: walk the BFS order backwards

start / 3

Subtree sizes for the snippet's tree. BFS order is 0 1 2 3 4 5 6; reversed, every vertex is finished before its parent adds it in — no recursion, so no stack overflow on a 200,000-vertex path.

C++

#include <print>
#include <utility>
#include <vector>

int main() {
    // Subtree sizes, bottom-up, without recursion.
    const std::size_t n = 7;
    std::vector<std::pair<std::size_t, std::size_t>> edges{{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5}, {5, 6}};
    std::vector<std::vector<std::size_t>> adj(n);
    for (auto [u, v] : edges) adj[u].push_back(v), adj[v].push_back(u);

    std::vector<std::size_t> order{0}, parent(n, n);
    std::vector<bool> seen(n, false);
    seen[0] = true;
    for (std::size_t k = 0; k < order.size(); ++k)
        for (std::size_t v : adj[order[k]])
            if (!seen[v]) seen[v] = true, parent[v] = order[k], order.push_back(v);

    std::vector<std::size_t> size(n, 1);
    for (std::size_t k = order.size(); k-- > 0;)        // reverse BFS order
        if (std::size_t u = order[k]; parent[u] != n) size[parent[u]] += size[u];
    for (std::size_t u = 0; u < n; ++u) std::print("{} ", size[u]);
    std::println();
}

Rerooting answers "the answer if the tree were rooted at every vertex" in O(n) total: one bottom-up pass computes subtree answers, then a top-down pass (BFS order, forwards) passes each vertex "everything outside my subtree". For the sum of distances to all vertices:

C++

// down[u] = Σ distances from u to its subtree; size[u] = subtree size (bottom-up pass)
// top-down: all[root] = down[root];
//           all[c] = all[parent] - size[c] + (n - size[c]);   // c's subtree gets 1 closer, the rest 1 farther

5. DAGs: topological order

Every DP is secretly a shortest/longest path problem on the DAG of its states. When the graph is given explicitly, the order is a topological order — no recursion, no memo table, just one pass.

Counting paths in topological order

start / 3

Edges only go to larger indices, so one pass from left to right finishes each vertex before anything reads it. Step through to fill the counts.

Faded example — your turn

Count the paths from vertex 0 to vertex n − 1 in a DAG whose vertices are already numbered in topological order (every edge goes from a smaller to a larger index). Fill in the loop body:

C++

std::vector<std::uint64_t> ways(n, 0);
ways[0] = 1;
for (std::size_t u = 0; u < n; ++u)
    for (std::size_t v : out[u])
        /* ??? */;
return ways[n - 1];

Answer

ways[v] += ways[u]; — every path to v ends with some edge u → v, and ways[u] is final by the time u is processed because all edges into u come from smaller indices.

6. Digits: the "tight" flag

"How many x ≤ N have property P?" for N up to 10¹⁸ can't loop over x. Walk N's digits from the most significant end instead. Every prefix built so far is either:

free — already smaller than N's prefix, so any next digit 0–9 keeps it smaller; or
tight — equal to N's prefix, so the next digit can't exceed N's digit.

The tight prefix branches into the free group with every digit below N's digit and stays tight with N's digit itself. Group the free prefixes by whatever P needs to remember (a digit sum, a remainder, the last digit…). Count of numbers ≤ N with no digit 4:

C++

#include <cstdint>
#include <print>
#include <string>

std::uint64_t without_four(std::uint64_t N) {
    std::uint64_t free = 0;   // prefixes already below N's prefix
    bool tight = true;        // N's own prefix still has no 4
    for (char ch : std::to_string(N)) {
        unsigned d = static_cast<unsigned>(ch - '0');
        free *= 9;                                   // any digit except 4
        if (tight) {
            free += d > 4 ? d - 1 : d;               // digits below d, skipping 4
            if (d == 4) tight = false;
        }
    }
    return free + (tight ? 1 : 0);                   // + N itself if it has no 4
}

int main() {
    std::println("{} {} {}", without_four(9), without_four(50), without_four(1'000'000'000'000'000'000));
}

Leading zeros are harmless here (0 isn't 4), and 0 itself is counted: the range is 0 ≤ x ≤ N. The final + 1 for N — the last tight prefix — is the classic thing to forget.

7. Making a recurrence faster

Sometimes the state space is fine but each transition scans too much.

Monotone queue. best[i] = a[i] + max(best[i−k..i−1]) is O(n·k) as written. The maximum of a sliding window is exactly what a monotonic deque gives in amortised O(1):

C++

#include <cstdint>
#include <deque>
#include <print>
#include <vector>

int main() {
    // Jump from index 0 to the last index, at most k steps at a time; maximise the sum of visited values.
    std::vector<std::int64_t> a{1, -1, -2, 4, -7, 3};
    const std::size_t k = 2;
    std::vector<std::int64_t> best(a.size());
    std::deque<std::size_t> window;                  // indices, best[] decreasing front to back
    for (std::size_t i = 0; i < a.size(); ++i) {
        while (!window.empty() && window.front() + k < i) window.pop_front();
        best[i] = a[i] + (window.empty() ? 0 : best[window.front()]);
        while (!window.empty() && best[window.back()] <= best[i]) window.pop_back();
        window.push_back(i);
    }
    std::println("{}", best.back());  // 1 → -1 → 4 → 3 = 7
}

Divide-and-conquer optimisation. In layered recurrences dp[j][i] = min over k < i of dp[j−1][k] + C(k, i), if the best k never moves left as i grows, solve the middle i first and recurse on each half with a narrowed k range: O(n log n) per layer instead of O(n²).

Convex hull trick. When each transition is a line evaluated at a point — dp[i] = min over j of (m_j · x_i + b_j) — keep the lower envelope of the lines. With slopes added in order and queries in order, a deque answers each in amortised O(1):

C++

// lines sorted by slope; drop a line when the new one makes it useless:
// bad(l1, l2, l3) = (b3 - b1) * (m1 - m2) <= (b2 - b1) * (m1 - m3)

These are worth knowing by name; reach for them only after the plain DP is correct and measured to be too slow.

Summary

Name the state first: two prefixes, an interval, a subset + position, a subtree, a DAG vertex, a digit position + tight flag.
The order must make every input ready: rows, interval length, increasing mask, reverse BFS, topological, most-significant digit first.
Reconstruction needs the table you'd walk back through; values alone can often live in a rolling row — remember the diagonal before overwriting it.
Never extend unreachable states, never shift a plain int 1 into a mask, and never recurse once per vertex of a tree that might be a path.

Color theme