Dynamic Programming I

The question

A courier's bag holds 10 kg. Five parcels are waiting, and each pays a fee on delivery:

Which parcels should go in the bag to earn the most? This is 0/1 knapsack: items $0..n-1$ with integer weights $w_i\ge 1$ and values $v_i\ge 0$, a capacity $W$, and a subset of total weight at most $W$ whose value is as large as possible. Each item is taken once or not at all.

This module is about a method more than a problem. Knapsack, independent sets on trees and longest increasing subsequences look unrelated, and each becomes a table once seven decisions are made. Prerequisites: Python, big-O notation and proof by induction; the doubling array from Amortized Analysis appears once, in the recap.

Trying everything, and trying greedily

With five parcels you can try all $2^5=32$ subsets. The best is parcels 0 and 4: weight 10, pay 23, and no other subset reaches it. The obvious shortcut, taking parcels in order of pay per kilogram while they fit, takes parcel 0 (2.5 per kg) and parcel 2 (2.4 per kg), then nothing else fits: 22.

from itertools import combinations
from functools import lru_cache

WTS, PAY, CAP = [4, 3, 5, 2, 6], [10, 7, 12, 3, 13], 10

def brute_force(wts, pay, cap):
    best = (0, ())
    for r in range(len(wts) + 1):
        for s in combinations(range(len(wts)), r):
            if sum(wts[i] for i in s) <= cap and sum(pay[i] for i in s) > best[0]:
                best = (sum(pay[i] for i in s), s)
    return best

def greedy_by_ratio(wts, pay, cap):
    load = total = 0
    for i in sorted(range(len(wts)), key=lambda i: -pay[i] / wts[i]):
        if load + wts[i] <= cap:
            load, total = load + wts[i], total + pay[i]
    return total

assert brute_force(WTS, PAY, CAP) == (23, (0, 4)) and greedy_by_ratio(WTS, PAY, CAP) == 22

Greedy is wrong because a good ratio can leave an awkward gap: after parcels 0 and 2 the bag has 1 kg left, and 1 kg earns nothing. Brute force is right but takes $2^n$ subsets, about ${10}^{18}$ at $n=60$.

Where does brute force waste its work? Write it as a recursion: the best pay from parcels $0..i-1$ with $c$ kg of room either skips parcel $i-1$ or takes it. On twenty parcels and a 50 kg bag, that recursion makes 710,746 calls, but it only ever asks 777 different questions. It answers the same question, "best from the first $i$ parcels with $c$ kg left", hundreds of times.

import random

rng = random.Random(9)
w20 = [rng.randint(1, 10) for _ in range(20)]
v20 = [rng.randint(1, 30) for _ in range(20)]
calls, asked = 0, set()

def plain(i, c):
    global calls
    calls += 1
    asked.add((i, c))
    if i == 0:
        return 0
    best = plain(i - 1, c)
    if w20[i - 1] <= c:
        best = max(best, plain(i - 1, c - w20[i - 1]) + v20[i - 1])
    return best

assert plain(20, 50) == 232 and calls == 710_746 and len(asked) == 777

Dynamic programming is the decision to answer each question once and write the answer down.

Seven decisions before any code

Every dynamic program in this course is designed by making the same seven decisions, in words, before writing a line:

The state is the decision that everything else hangs on. If you cannot say what one cell means, you cannot check the recurrence, and "what does this cell mean?" is the first question to ask of any DP you debug.

The proof is always the same induction in evaluation order. The recurrence reads only entries written earlier, which are correct by induction. Its cases are exhaustive: every feasible solution of the subproblem falls into one case. And within a case, the best solution is that case's choice plus an optimal solution of a smaller state. If the rest were not optimal, swapping in a better rest would improve the whole (an exchange argument). That shows the optimum is at most what the recurrence computes. Conversely, every candidate the recurrence compares is a real solution (a case's choice added to a feasible solution of a smaller state), so the recurrence never exceeds the optimum. The two bounds meet.

Knapsack, decided

• State: $T[i][c]$ is the best pay using only parcels $0..i-1$ with room $c$, for $0\le i\le n$ and $0\le c\le W$.
• Recurrence: $$T[i][c]=max(T[i-1][c],T[i-1][c-w_{i-1}]+v_{i-1}),$$ the second option only when $w_{i-1}\le c$. An optimal subset for $(i,c)$ either leaves parcel $i-1$ out, and then the rest is optimal for $(i-1,c)$, or contains it, and then the rest is optimal for $(i-1,c-w_{i-1})$. Those two cases cover every subset. Conversely, both options are achieved by real subsets: $T[i-1][c]$ by one that fits in $c$, and the second option by adding parcel $i-1$ to one that fits in $c-w_{i-1}$.
• Base case: $T[0][c]=0$ for every $c$: no parcels, no pay.
• Evaluation order: $i$ increasing. Row $i$ reads only row $i-1$, so the order within a row does not matter.
• Answer location: $T[n][W]$.
• Reconstruction: walk back from $(n,W)$. If $T[i][c]\ne T[i-1][c]$, parcel $i-1$ was needed: record it and subtract its weight from $c$. Then move to row $i-1$.
• Space: one row of $W+1$ cells is enough for the value (next section), but this walk back needs every row.

The seven decisions translate almost word for word into a recursion that remembers its answers. This version asks only the questions it needs; the lab fills the whole table bottom-up instead, in the evaluation order above.

@lru_cache(maxsize=None)
def best(i, c):
    """T[i][c]: the best pay from parcels 0..i-1 with room c."""
    if i == 0:
        return 0
    skip = best(i - 1, c)
    if WTS[i - 1] > c:
        return skip
    return max(skip, best(i - 1, c - WTS[i - 1]) + PAY[i - 1])

table = [[best(i, c) for c in range(CAP + 1)] for i in range(len(WTS) + 1)]
assert table[3] == [0, 0, 0, 7, 10, 12, 12, 17, 19, 22, 22]
assert table[5] == [0, 0, 3, 7, 10, 12, 13, 17, 19, 22, 23]

The table, filled and walked back

Here is the whole table for the courier. Row $i$ has considered parcels $0..i-1$, and column $c$ is the room left.

The answer 23 sits in the bottom-right corner. It came from $T[4][4]+13=23$, which beats $T[4][10]=22$, so parcel 4 was taken and the walk moves to room $10-6=4$. In rows 4, 3 and 2 the value at room 4 does not change (10, 10, 10), so parcels 3, 2 and 1 were skipped. At row 1 the value drops from 10 to 0, so parcel 0 was taken. The subset is $\{0,4\}$.

assert table[4][4] + PAY[4] == 23 > table[4][10] == 22 and CAP - WTS[4] == 4
assert [table[i][4] for i in (4, 3, 2, 1, 0)] == [10, 10, 10, 10, 0]
assert brute_force(WTS, PAY, CAP)[1] == (0, 4)

Space. The value alone needs one row, updated in place. Scan the room $c$ downwards, from $W$ to $w_{i-1}$, so that $c-w_{i-1}$ still holds the previous row's value when it is read. An upward scan reads a cell that this parcel has already updated, so the parcel can be taken twice. With one parcel of weight 2 and pay 3 and a 4 kg bag, the upward scan answers 6 and the right answer is 3. The plain one-row version gives up the walk back above, because the rows it compares have been overwritten. Reconstruction does not need every value, though. Store one take-or-skip bit per cell, $n(W+1)$ bits instead of $n(W+1)$ words, and walk back along the bits. Or split the parcels in half, run one row forwards over the first half and one row backwards over the second, pick the room split that maximises the sum, and recurse on each half: $O(n+W)$ words of space for about twice the time.

Why $O(nW)$ is not polynomial

The table has $(n+1)(W+1)$ cells and each costs a constant number of word operations, so the time is $\Theta (nW)$ in the worst case on a word-RAM. That looks polynomial, but it isn't polynomial in the right thing. The input writes $W$ in about ${\log }_{2}W$ bits, and $W$ itself is exponential in that. Multiply every weight and the capacity by 10: the answer is still 23, each number grows by about 3.3 bits, and the table grows tenfold.

def input_bits(scale):
    return sum((w * scale).bit_length() for w in WTS) + (CAP * scale).bit_length() \
        + sum(v.bit_length() for v in PAY)

@lru_cache(maxsize=None)
def scaled(i, c, s):
    if i == 0:
        return 0
    skip = scaled(i - 1, c, s)
    return skip if WTS[i - 1] * s > c else max(skip, scaled(i - 1, c - WTS[i - 1] * s, s) + PAY[i - 1])

rows = [(s, input_bits(s), 5 * (CAP * s + 1), scaled(5, CAP * s, s)) for s in (1, 10, 100, 1000)]
assert rows == [(1, 34, 55, 23), (10, 52, 505, 23), (100, 72, 5005, 23), (1000, 92, 50005, 23)]

The input grows by about 20 bits per step, and the work grows by a factor of 10 per step: exponential in the input's length. An algorithm that is polynomial in the numeric values but not in their bit length is called pseudo-polynomial. It is excellent when $W$ is a few thousand kilograms and useless when $W$ is a 64-bit byte count. Nobody expects to do much better: 0/1 knapsack is NP-hard, so a truly polynomial algorithm would give one for every problem in NP.

Two states per node: independent sets on a tree

A charity runs its volunteers as a tree: node 0 is the coordinator, and every other volunteer has exactly one supervisor. It wants a team with no volunteer next to their own supervisor, and each volunteer has a weight (hours they can give). This is maximum-weight independent set on a tree: pick nodes, no node together with its parent, with total weight as large as possible.

Try one number per node, "the best total in $u$'s subtree". The parent can't use it, because it doesn't say whether $u$ itself was picked, and that is exactly what the parent's rule needs to know. On a coordinator of weight 5 with one volunteer of weight 4, adding "best below" to the coordinator's weight gives $5+4=9$, a team that breaks the rule. So the state carries that bit of information:

• State: two numbers per node. $\mathrm{i}\mathrm{n}\mathrm{c}(u)$ is the best weight in $u$'s subtree with $u$ picked, and $\mathrm{e}\mathrm{x}\mathrm{c}(u)$ is the best with $u$ not picked.
• Recurrence: $\mathrm{i}\mathrm{n}\mathrm{c}(u)=w(u)+{\sum }_c\mathrm{e}\mathrm{x}\mathrm{c}(c)$ and $\mathrm{e}\mathrm{x}\mathrm{c}(u)={\sum }_{c}max(\mathrm{i}\mathrm{n}\mathrm{c}(c),\mathrm{e}\mathrm{x}\mathrm{c}(c))$ over $u$'s children $c$. Picking $u$ rules out its children and nothing else. Different children's subtrees share no edge, so once $u$'s status is fixed they are independent.
• Base case: a leaf has $\mathrm{i}\mathrm{n}\mathrm{c}=w(u)$ and $\mathrm{e}\mathrm{x}\mathrm{c}=0$ (empty sums).
• Evaluation order: children before parents (post-order).
• Answer location: $max(\mathrm{i}\mathrm{n}\mathrm{c}(r),\mathrm{e}\mathrm{x}\mathrm{c}(r))$ at the root $r$.
• Reconstruction: top-down, carrying "may this node be picked?". Pick $u$ if it may be and $\mathrm{i}\mathrm{n}\mathrm{c}(u)>\mathrm{e}\mathrm{x}\mathrm{c}(u)$. The children of a picked node may not be picked.
• Space: two numbers per node, $O(n)$ time and space. The value alone can fold each child's pair into its parent's running sums as soon as the child is done, so only the $O(\text{height})$ sums along the current path stay live; reconstruction reads every node's pair, so it keeps all $n$.

The root's pair is $(16,22)$, so the answer is 22. Reconstruction starts at the root: $16<22$, so the coordinator is not picked. Node 1 has $(3,2)$ and is picked. Node 2 has $(8,2)$ and is picked. Node 3 has $(7,11)$ and is not, so its children 7 and 8 may be, and both are. The team $\{1,2,7,8\}$ weighs 22. Picking every other level gives 16 or 18. Picking the heaviest volunteer who still fits, over and over, takes 2 (weight 8), then 3 (weight 7), then 1, and gets 18.

The numbers above are checked here by brute force over every team inside each subtree, a deliberate stand-in: writing the linear-time version is the lab's job.

KIDS = {0: [1, 2, 3], 1: [4, 5], 2: [6], 3: [7, 8]}
HOURS = [1, 3, 8, 7, 1, 1, 2, 6, 5]
PARENT = {c: p for p, cs in KIDS.items() for c in cs}

def subtree(u):
    return [u] + [x for c in KIDS.get(u, []) for x in subtree(c)]

def best_team(nodes, must=None, never=None):
    top = 0
    for r in range(len(nodes) + 1):
        for s in combinations(nodes, r):
            if any(PARENT.get(x) in s for x in s) or (must is not None and must not in s) \
                    or (never is not None and never in s):
                continue
            top = max(top, sum(HOURS[x] for x in s))
    return top

pairs = [(best_team(subtree(u), must=u), best_team(subtree(u), never=u)) for u in range(9)]
assert pairs == [(16, 22), (3, 2), (8, 2), (7, 11), (1, 0), (1, 0), (2, 0), (6, 0), (5, 0)]
assert sum(HOURS[x] for x in (1, 2, 7, 8)) == 22
assert sum(HOURS[x] for x in (0, 4, 5, 6, 7, 8)) == 16 and sum(HOURS[x] for x in (1, 2, 3)) == 18

def heaviest_first(nodes):
    team = []
    for u in sorted(nodes, key=lambda u: -HOURS[u]):
        if PARENT.get(u) not in team and not any(PARENT.get(x) == u for x in team):
            team.append(u)
    return team, sum(HOURS[x] for x in team)

assert heaviest_first(range(9)) == ([2, 3, 1], 18)
assert heaviest_first(range(8, -1, -1))[1] == 18      # the same whichever way ties are broken

Longest increasing subsequence in $O(n^2)$

A sequence of twelve readings:

A subsequence keeps the order of the positions and may skip any of them. It is not a contiguous block: $17,23,35$ skips 58 and 61. We want the longest one that is strictly increasing.

• State: $L[i]$ is the length of the longest increasing subsequence ending at index $i$.
• Recurrence: $L[i]=1+max\{L[j]:j<i,a_j<a_i\}$. A subsequence ending at $a_i$ is either $a_i$ alone or some subsequence ending at an earlier, smaller $a_j$ with $a_i$ appended.
• Base case: when no earlier $a_j$ is smaller, the max is empty and counts as 0, so $L[i]=1$: $a_i$ alone.
• Evaluation order: $i$ increasing.
• Answer location: ${max}_{i}L[i]$, not $L[n-1]$. On $[3,4,1]$, $L[2]=1$ but the answer is 2.
• Reconstruction: store the $j$ that gave the max, and follow those links back.
• Space: $O(n)$, and none of it can be dropped: a later $i$ may read any earlier $L[j]$, and the answer is a max over all of $L$.

A = [42, 17, 58, 23, 61, 35, 19, 70, 44, 52, 27, 66]

def lis_quadratic(a):
    L, link = [1] * len(a), [None] * len(a)
    for i in range(len(a)):
        for j in range(i):
            if a[j] < a[i] and L[j] + 1 > L[i]:
                L[i], link[i] = L[j] + 1, j
    i = max(range(len(a)), key=L.__getitem__) if a else None
    out = []
    while i is not None:
        out.append(a[i])
        i = link[i]
    return L, out[::-1]

L, sub = lis_quadratic(A)
assert L == [1, 1, 2, 2, 3, 3, 2, 4, 4, 5, 3, 6] and sub == [17, 23, 35, 44, 52, 66]
assert lis_quadratic([3, 4, 1])[0][-1] == 1

The inner loop runs $j=0..i-1$ whatever the data, so this makes exactly $n(n-1)/2$ comparisons $a_j<a_i$: 66 here, and about $5·{10}^9$ for $n={10}^5$.

Faster: the tails array

The quadratic DP asks, for each new element, "which earlier subsequences can I extend?" and looks at all of them. Most of that is wasted. Among subsequences of the same length, only the one with the smallest last value matters, because it is the easiest to extend. So keep one number per length:

To read the next element $x$, find the first slot $k$ with tails[k] $\ge x$ by binary search (it is sorted), and put $x$ there, or append $x$ if there is no such slot. The answer is the length of tails.

Why the invariant survives. Suppose it holds before $x$. For slots $j<k$, tails[j] $<x$, so a subsequence ending in $x$ can't lower them. At slot $k$, tails[k-1] $<x$, so $x$ extends a subsequence of length $k$, and $x\le$ tails[k], so $x$ is the new smallest. For $j>k$, ending at $x$ with length $j+1$ would need a subsequence of length $j$ ending below $x$, but every such subsequence ends at a value $\ge$ tails[j-1] $\ge$ tails[k] $\ge x$. And $x$ lands between tails[k-1] and the old tails[k], so tails stays sorted.

The step not to skip: the final tails array is not an answer. It mixes the ends of different candidates, and here 27 (position 10) comes after 44 (position 8). To recover a real subsequence, remember a link whenever $x$ lands in slot $k$: the position of the element in slot $k-1$ at that moment. Following links back from the element in the last slot gives a longest increasing subsequence.

The check below computes tails straight from the invariant's definition, using $L$ from the quadratic DP: tails[k] is the smallest $a_i$ in the prefix with $L[i]\ge k+1$, because a subsequence of length $L[i]$ ending at $a_i$ contains one of every shorter length ending there. It is a stand-in that confirms the figure. The binary-search version is the lab's.

def tails_by_definition(a, upto):
    L = lis_quadratic(a[:upto])[0]
    return [min(a[i] for i in range(upto) if L[i] >= k + 1) for k in range(max(L))]

assert tails_by_definition(A, 6) == [17, 23, 35] and tails_by_definition(A, 7) == [17, 19, 35]
assert tails_by_definition(A, 11) == [17, 19, 27, 44, 52]
assert tails_by_definition(A, 12) == [17, 19, 27, 44, 52, 66]
assert A.index(27) > A.index(44)       # so the final tails is not a subsequence of A

Cost. With $\ell$ elements in tails, a binary search makes at most $\lceil {\log }_2(\ell +1)\rceil$ comparisons, so the total is at most $n\lceil {\log }_2(n+1)\rceil$: $O(n\log n)$ in the worst case, in the comparison model. That matches a known lower bound: in the comparison model, the longest increasing subsequence needs $\Omega (n\log n)$ comparisons in the worst case (Fredman, 1975; stated here, not proved).

Measure the claim

Counting comparisons on seeded random arrays (the course's verification script, tools/verify/unit3.py, computes these):

The ratio in the last column is flat, as an $n\log n$ bound predicts, and well under the worst-case constant 1 because tails stays short on random input (its length grows like $2\sqrt{n}$). These are measurements on these inputs, not a theorem about all inputs. The quadratic column is exact for every input.

import math

assert [n * (n - 1) // 2 for n in (1000, 10_000, 100_000)] == [499_500, 49_995_000, 4_999_950_000]
assert [round(c / (n * math.log2(n)), 3)
        for n, c in ((1000, 5251), (10_000, 69_181), (100_000, 858_880))] == [0.527, 0.521, 0.517]

A problem that looks different

A post office sells stamps worth 1, 7 and 10 cents. What is the fewest stamps that make exactly 14 cents? Taking the largest stamp that fits gives $10+1+1+1+1$, five stamps. Two are enough. What would one table entry mean, and where is the answer? The lab's last problem is a different one.

Practise

In the lab you fill a knapsack table cell by cell, with each cell's dependencies drawn as arrows and the recurrence checked in every frame, then walk it back. You predict and then watch the tails array on a new sequence, write the two-state tree DP with reconstruction for a new tree, measure the pseudo-polynomial table and the two subsequence methods on the lab's own seeds, and finish with one problem that does not say what it is.

Recap

• You can now: name the seven DP decisions for a new problem; fill, walk back and space-optimize a knapsack table; solve independent set on a tree with two states per node; and find a longest increasing subsequence in $O(n\log n)$, recovering the subsequence with links.
• Invariant: each entry equals the optimum of exactly its state's subproblem, because the recurrence's case split is exhaustive and reads only entries written earlier. For tails: slot $k$ holds the smallest end of an increasing subsequence of length $k+1$.
• Complexity achieved: knapsack $\Theta (nW)$ time, pseudo-polynomial (against $2^n$ subsets); the tree in $O(n)$ (against $2^n$ teams); the longest increasing subsequence in at most $n\lceil {\log }_2(n+1)\rceil$ comparisons (against $n(n-1)/2$), all worst case.
• Failure mode: the one-row knapsack scanned upwards quietly lets every parcel be taken again and again; returning the final tails as the subsequence.
• In real software: Python's bisect.bisect_left is the binary search the tails method uses. Git's --patience diff (xdiff/xpatience.c) matches lines that are unique in both files and keeps a longest increasing subsequence of the matches, found with a binary search over sorted pile ends.
• Retrieval: (Amortized Analysis) tails only ever grows by appending. If it were an array that doubles its capacity when full, what would $n$ appends cost in copying?

Check yourself

1. Why is the knapsack recurrence correct, and why must the table be walked back instead of read off the last row?
2. Each parcel may now be taken any number of times. What changes in the recurrence and in the one-row loop, and on which instance do the two answers differ?
3. For $n={10}^5$ random numbers, compare the quadratic DP with the tails method, and say whether either computes the longest increasing contiguous block.

Topic list modeled on the public schedule of CMU 15-451/651 Algorithm Design and Analysis (Fall 2025). All lecture text, proofs, examples, code, and exercises are original to SciMigo; no CMU course materials are reproduced. This course is independent and not affiliated with or endorsed by Carnegie Mellon University.