Dynamic programming I

Dynamic programming (DP) is recursion that refuses to solve the same subproblem twice. When a problem has optimal substructure (the best answer is built from best answers to smaller versions) and overlapping subproblems (those smaller versions repeat), you can store each answer once in a table and go from exponential time to polynomial.

The skill isn't memorising problems. It's a recipe:

1. Name the state in words. "best[a] = the fewest coins that sum to exactly a." If you can't say it in one sentence, you can't code it.
2. Write the recurrence: how a state is built from smaller ones.
3. Fix the base cases: the states that need no smaller state.
4. Choose an order that computes every state after the states it needs.
5. Optionally shrink the table to the part you still need.

1. From exponential to linear: the same function four times

Fibonacci is the classic demonstration. Count how many calls each version makes:

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

long calls = 0;

std::uint64_t fib_naive(int n) {
    ++calls;
    return n < 2 ? n : fib_naive(n - 1) + fib_naive(n - 2);
}

std::uint64_t fib_memo(int n, std::vector<std::uint64_t>& memo) {   // top-down
    ++calls;
    if (n < 2) return n;
    if (memo[n] != 0) return memo[n];
    return memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo);
}

std::uint64_t fib_table(int n) {                                     // bottom-up
    std::vector<std::uint64_t> f(n + 2);
    f[1] = 1;
    for (int i = 2; i <= n; ++i) f[i] = f[i - 1] + f[i - 2];
    return f[n];
}

std::uint64_t fib_rolling(int n) {                                   // O(1) space
    std::uint64_t a = 0, b = 1;
    for (int i = 0; i < n; ++i) { std::uint64_t next = a + b; a = b; b = next; }
    return a;
}

int main() {
    calls = 0;
    std::println("naive   fib(25) = {}  ({} calls)", fib_naive(25), calls);
    std::vector<std::uint64_t> memo(26);
    calls = 0;
    std::println("memo    fib(25) = {}  ({} calls)", fib_memo(25, memo), calls);
    std::println("table   fib(90) = {}", fib_table(90));
    std::println("rolling fib(90) = {}", fib_rolling(90));
}

• Naive recursion recomputes fib(23) twice, fib(22) three times, and so on: about φⁿ calls.
• Memoization (top-down) keeps the recursive shape but caches answers. Each state is computed once; every other call is a lookup.
• Tabulation (bottom-up) fills the table in an order where dependencies are always ready. No recursion, so no stack depth limit.
• Space optimisation: the recurrence only looks two entries back, so keep just those two ("rolling" variables or rows).

Top-down is often easier to write first; bottom-up is usually faster and can't overflow the stack (remember the 8 MiB limit from the recursion skill).

2. One-dimensional DP: coins

Fewest coins. State: best[a] = fewest coins summing to exactly a. Recurrence: the last coin is some coin c ≤ a, so best[a] = 1 + min over c of best[a − c]. Base case: best[0] = 0. Order: a ascending. Unreachable amounts need a value that means "impossible" — and must never be extended (adding 1 to INT_MAX is signed overflow).

Worked example

#include <algorithm>
#include <climits>
#include <optional>
#include <print>
#include <vector>

std::optional<int> min_coins(const std::vector<int>& coins, int amount) {
    std::vector<int> best(amount + 1, INT_MAX);   // INT_MAX = impossible
    best[0] = 0;
    for (int a = 1; a <= amount; ++a)
        for (int c : coins)
            if (c <= a && best[a - c] != INT_MAX)   // never extend "impossible"
                best[a] = std::min(best[a], best[a - c] + 1);
    if (best[amount] == INT_MAX) return std::nullopt;
    return best[amount];
}

int main() {
    std::vector<int> coins{1, 3, 4};
    std::println("6 → {}", min_coins(coins, 6).value());   // 3 + 3, greedy would say 4 + 1 + 1
    std::println("0 → {}", min_coins(coins, 0).value());
    std::vector<int> evens{2, 4};
    std::println("7 possible? {}", min_coins(evens, 7).has_value());
}

Greedy (take the biggest coin first) gives 3 coins for 6 here; DP considers every last coin and finds 2.

Counting ways — and why loop order is meaning. "How many ways to make a?" has two different answers depending on whether order matters:

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

int main() {
    std::vector<int> coins{1, 2, 3};
    const int target = 4;

    // Coins OUTER: each coin is added in a fixed order → multisets.
    std::vector<std::uint64_t> combos(target + 1, 0);
    combos[0] = 1;
    for (int c : coins)
        for (int a = c; a <= target; ++a) combos[a] += combos[a - c];

    // Amounts OUTER: any coin can come last → ordered sequences.
    std::vector<std::uint64_t> sequences(target + 1, 0);
    sequences[0] = 1;
    for (int a = 1; a <= target; ++a)
        for (int c : coins)
            if (c <= a) sequences[a] += sequences[a - c];

    std::println("multisets: {}  sequences: {}", combos[target], sequences[target]);
}

{1,1,2} is one multiset but three sequences (112, 121, 211). With coins outer, when you process coin c the table only knows about coins before it, so every multiset is built in one canonical order.

Counts grow fast — use std::uint64_t (or work modulo a prime when the problem says so). With eight coin values and an amount of 5 000 the count already exceeds 32 bits.

3. Two-dimensional DP: grids

Cheapest path from the top-left to the bottom-right cell, moving right or down. State: cost[r][c] = cheapest path sum ending at (r, c). Recurrence: you arrived from above or from the left, cost[r][c] = grid[r][c] + min(cost[r−1][c], cost[r][c−1]). Base cases: the first row can only be reached from the left, the first column only from above.

Each row only needs the row above, so one row of storage is enough: before you overwrite row[c] it still holds the value above; row[c − 1] already holds the value to the left in the current row.

for (std::size_t r = 0; r < rows; ++r)
    for (std::size_t c = 0; c < cols; ++c) {
        std::int64_t cell = grid[r][c];
        if (r == 0 && c == 0) row[c] = cell;
        else if (r == 0)      row[c] = row[c - 1] + cell;          // only from the left
        else if (c == 0)      row[c] = row[c] + cell;              // only from above
        else                  row[c] = std::min(row[c], row[c - 1]) + cell;
    }

Obstacles ("count paths avoiding blocked cells") are the same table with ways[r][c] = 0 on blocked cells and ways = above + left elsewhere.

4. 0/1 knapsack and the downward loop

Items with weights and values; each may be taken at most once; maximise value within a weight capacity. State over the first i items: best[i][c] = best value using items 0..i−1 with total weight ≤ c. Recurrence: skip item i, or take it if it fits: best[i+1][c] = max(best[i][c], best[i][c − w] + v).

Row i + 1 only reads row i, so one row suffices — if you iterate the capacity downward. Going down, best[c − w] hasn't been updated for the current item yet, so it still means "without this item". Going up, it may already include the item, and you've solved a different problem (unbounded knapsack, where items can repeat):

#include <print>
#include <vector>

int main() {
    std::vector<int> w{2}, v{10};
    const int cap = 6;
    std::vector<int> down(cap + 1, 0), up(cap + 1, 0);
    for (std::size_t i = 0; i < w.size(); ++i) {
        for (int c = cap; c >= w[i]; --c) down[c] = std::max(down[c], down[c - w[i]] + v[i]);
        for (int c = w[i]; c <= cap; ++c) up[c] = std::max(up[c], up[c - w[i]] + v[i]);
    }
    std::println("downward (each item once): {}", down[cap]);
    std::println("upward (item reused):      {}", up[cap]);
}

Value vs solution. One row gives the best value. To report which items, remember the decisions: a bit take[i][c] set when item i improved capacity c. Then walk back from the last item: if take[i][c], item i is in the answer and c -= w[i].

5. Longest increasing subsequence

The longest strictly increasing subsequence (elements in order, not necessarily adjacent). The O(n²) DP: len[i] = length of the longest increasing subsequence ending at i = 1 + max len[j] over j < i with v[j] < v[i].

The O(n log n) version keeps a different state: tails[k] = the smallest possible last element of an increasing subsequence of length k + 1. tails is always sorted, so each new x finds its place with a binary search: the first tail ≥ x is replaced by x (same length, smaller end — strictly better), or x extends the longest run if it's bigger than every tail.

#include <algorithm>
#include <print>
#include <vector>

int main() {
    std::vector<int> v{3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
    std::vector<int> tails;
    for (int x : v) {
        auto it = std::ranges::lower_bound(tails, x);   // first tail >= x
        if (it == tails.end()) tails.push_back(x);
        else *it = x;
    }
    std::println("LIS length {}  (tails at the end: {})", tails.size(), tails);
}

tails is not an increasing subsequence of the input — only its length is meaningful. lower_bound (first ≥ x) makes the subsequence strictly increasing; upper_bound (first > x) would allow equal neighbours.

Faded example — your turn

House robber: houses in a row with amounts m[i]; you can't take two adjacent houses. Fill in the state and recurrence, then roll it into two variables.

// best[i] = most money from houses 0..i (state in words — finish it)
// best[i] = max( ??? , ??? )
std::int64_t take_prev2 = 0, take_prev1 = 0;
for (int x : m) {
    std::int64_t cur = /* ??? */;
    take_prev2 = take_prev1;
    take_prev1 = cur;
}

6. Checklist

• Overlapping subproblems? Draw the recursion tree for a small input; if the same arguments appear more than once, DP pays off.
• The state must capture everything the future needs. If two different histories with the same state could lead to different best answers, the state is too small (e.g. knapsack needs the remaining capacity, not just the item index).
• Iteration order must compute dependencies first — and in 1-D rolled tables it decides which problem you solve (multisets vs sequences, 0/1 vs unbounded).
• Sentinels: never do arithmetic on "impossible".
• Overflow: counts and sums need 64 bits (or a modulus).
• Reconstruction needs the decisions, not just the values.

Summary

• DP = recursion + "solve each state once".
• Recipe: state in words → recurrence → base cases → order → shrink.
• Loop order in rolled tables is semantics: coins-outer counts multisets; downward capacity keeps 0/1 knapsack 0/1.
• LIS in O(n log n) with sorted tails and lower_bound.
• Use 64-bit counts and sums; never extend an "impossible" sentinel.