4 · Dynamic programming

DPV Ch 6 + lectures 27–29 + HW4 P6–P7. Two exam problems come from here. Expect either "fill this table" (knapsack, edit distance, LCS, LIS) or "design a DP" for a DPV exercise (6.1–6.11 style). Every table and number on this page was computed by script.

Router

If the question says…	Subproblem shape	Go to
one sequence, "longest / best subsequence", "ending at"	prefix, ending at j	LIS, 6.1, 6.2, 6.3, 6.4
two strings	two prefixes $(i, j)$	edit distance, LCS (6.11), substring (6.8)
capacity / weight limit W, integer weights	capacity $w$ (and items $1..j$ if each item once)	knapsack
"order of operations", "parenthesize", "where to cut a segment", palindrome	interval $(i, j)$	chain matrix, 6.7, 6.9
tree	subtree of $u$ (in / out)	independent set in a tree
weighted intervals	first $k$ by finish time	weighted interval scheduling
rod / length $n$, sell pieces	length $j$	rod cutting, HW4 P6

1 · The recipe

Subproblem in words. "$T[i]$ = the best ____ using only ____ / ending exactly at ____." This is the creative step.
Recurrence by guessing one choice. Last element? Previous element? Item $j$ in or out? Where is the last split? Write one case per possible answer and take max/min.
Base cases, and where the final answer sits ($T[n]$, $T[n, m]$, $\max_j T[j]$, …).
Fill order: every entry is computed after the entries it reads.
Cost = #subproblems × work per subproblem. Keep back-pointers (which case won) to rebuild the actual solution.

DP = shortest (or longest) path in a hidden DAG. Nodes = subproblems; edge $u \to v$ when $v$'s recurrence reads $u$; fill order = a topological order; value of an entry = best path to that node; back-pointers = following prev. If the dependencies form a cycle, there is no valid order and the recipe fails (that is why longest simple path in a general graph is hard but easy in a DAG).

Three components (lecture 27): simple subproblems, subproblem optimality (an optimal solution is built from optimal subsolutions), subproblem overlap (store answers, solve each once). Top-down memoization and bottom-up tables solve the same subproblems in the same big-O time.

How to write a DP answer for full marks.

Define the table in one sentence with index ranges: "For $0 \le j \le n$, let $P(j)$ = the minimum total penalty of a trip that ends at hotel $j$."
Recurrence with every case, plus one justification sentence: "The last day starts at some hotel $i < j$; the part before it must itself be optimal (cut and paste)."
Base cases written out ($P(0) = 0$, $E(i, 0) = i$, …).
Order + answer: "Fill $j = 1, \dots, n$; return $P(n)$."
Running time and space: "$n$ subproblems × $O(n)$ each = $O(n^2)$ time, $O(n)$ space."
Recover the solution: "Store the $i$ that achieves the min in prev($j$); follow prev from $n$ back to 0."
Short DPV-style pseudocode if the question says "give an algorithm".

Missing the definition in words or the running time is where points usually go.

2 · Longest increasing subsequence

$$L(j) = 1 + \max\{L(i) : i < j,\ a_i < a_j\} \quad(\max \emptyset = 0)$$

$L(j)$ = length of the longest increasing subsequence ending exactly at $a_j$. Answer $\max_j L(j)$. Order $j = 1..n$. $n$ subproblems × $O(n)$ = $O(n^2)$. "Ending at j" is needed because extending a subsequence needs to know its last element.

j	1	2	3	4	5	6	7	8
$a_j$	5	2	8	6	3	6	9	7
$L(j)$	1	1	2	2	2	3	4	4
prev	–	–	1	1	2	5	6	6

Answer 4. Rebuild from $j = 7$: 9 ← 6 (j=6) ← 3 (j=5) ← 2 (j=2): 2, 3, 6, 9. (2, 3, 6, 7 also has length 4.) prev = the first $i$ achieving the max.

3 · Edit distance

$$E(i, j) = \min\{\,E(i-1, j) + 1,\ \ E(i, j-1) + 1,\ \ E(i-1, j-1) + \text{diff}(i, j)\,\}$$

$E(i, j)$ = edit distance between $x[1..i]$ and $y[1..j]$. Cases = last column of the alignment: delete $x_i$, insert $y_j$, or match/substitute. diff = 0 if $x_i = y_j$, else 1. Base $E(i, 0) = i$, $E(0, j) = j$. Answer $E(m, n)$. $O(mn)$ time. With general costs: insert $\alpha$, delete $\beta$, substitute $\gamma$, base $E(0,j) = j\alpha$, $E(i,0) = i\beta$.

SNOWY (rows) → SUNNY (columns):

	–	S	U	N	N	Y
–	0	1	2	3	4	5
S	1	0	1	2	3	4
N	2	1	1	1	2	3
O	3	2	2	2	2	3
W	4	3	3	3	3	3
Y	5	4	4	4	4	3

Edit distance 3. One optimal alignment: S–NOWY over SUNN–Y (insert U, substitute O→N, delete W). Any of row-by-row, column-by-column or anti-diagonal fill works: each cell reads up, left, and up-left. Only the distance needed → keep two rows, $O(\min(m,n))$ space.

Boundary trap (lecture correction): boundary entries are $j\alpha$ and $i\beta$, not ∞. Return Opt[n, m].

4 · Longest common subsequence (DPV 6.11)

$$c[i, j] = \begin{cases} c[i-1, j-1] + 1 & \text{if } x_i = y_j \\ \max\{c[i-1, j],\ c[i, j-1]\} & \text{otherwise} \end{cases}$$

$c[i, j]$ = length of an LCS of $x[1..i]$ and $y[1..j]$. Base $c[i, 0] = c[0, j] = 0$. Fill row by row. Answer $c[m, n]$. $\Theta(mn)$ time; $O(\min(m,n))$ space if only the length is needed.

x = ABCBDAB (rows), y = BDCABA (columns):

	B	D	C	A	B	A
–	0	0	0	0	0	0
A	0	0	0	1	1	1
B	1	1	1	1	2	2
C	1	1	2	2	2	2
B	1	1	2	2	3	3
D	1	2	2	2	3	3
A	1	2	2	3	3	4
B	1	2	2	3	4	4

LCS length 4. Trace back from the corner (diagonal on a match; otherwise move to the larger neighbor, up on ties): BCBA.

Proof idea (cut and paste, lecture). If $x_i = y_j$, an LCS $z[1..k]$ ends with that letter, and $z[1..k-1]$ must be an LCS of the shorter prefixes; a longer one plus $z_k$ would beat $z$. If $x_i \ne y_j$, $z$ skips $x_i$ or skips $y_j$, giving the two max terms.

DPV 6.11 exam answer: exactly the above with $x = x_1..x_n$, $y = y_1..y_m$: $(n+1)(m+1)$ entries, $O(1)$ each, $O(mn)$.

5 · 0/1 knapsack

$$B[k, w] = \begin{cases} B[k-1, w] & \text{if } w_k > w \\ \max\{B[k-1, w],\ B[k-1, w - w_k] + b_k\} & \text{otherwise} \end{cases}$$

$B[k, w]$ = max benefit using only items $1..k$ with total weight $\le w$. Base $B[0, w] = 0$. Answer $B[n, W]$. $O(nW)$: pseudo-polynomial (polynomial in the value $W$, exponential in its number of bits).

Lecture example, $W = 9$: items (w, b) = 1 (4, 20), 2 (2, 3), 3 (2, 6), 4 (6, 25), 5 (2, 80).

after	2	3	4	5	6	7	8	9
k=1	0	0	20	20	20	20	20	20
k=2	3	3	20	20	23	23	23	23
k=3	6	6	20	20	26	26	29	29
k=4	6	6	20	20	26	26	31	31
k=5	80	80	86	86	100	100	106	106

Answer 106. Which items: $B[5,9] = 106 \ne B[4,9] = 31$ → take 5, go to $w = 7$. $B[4,7] = B[3,7] = 26$ → skip 4. $B[3,7] = 26 \ne B[2,7] = 23$ → take 3, $w = 5$. $B[2,5] = B[1,5]$ → skip 2. $B[1,5] = 20 \ne 0$ → take 1. Items {1, 3, 5}, weight 8.

1-D array trick. Row $k$ reads only row $k - 1$, so keep one array and run $w$ downward:

for w = 0 to W: B[w] = 0
for k = 1 to n:
    for w = W down to w_k:
        if B[w − w_k] + b_k > B[w]: B[w] = B[w − w_k] + b_k

Downward keeps $B[w - w_k]$ at its row-$(k-1)$ value, so each item is used at most once. Running $w$ upward lets item $k$ be reused: that is exactly knapsack with repetition.

6 · Knapsack with repetition (DPV §6.4)

$$K(w) = \max_{i:\, w_i \le w}\{K(w - w_i) + v_i\},\qquad K(0) = 0$$

Guess the last item added. $W + 1$ subproblems × $O(n)$ = $O(nW)$. No item index needed because any item may be used again.

DPV example, $W = 10$: item 1 (6, $30), item 2 (3, $14), item 3 (4, $16), item 4 (2, $9).

w	0	1	2	3	4	5	6	7	8	9	10
K(w)	0	0	9	14	18	23	30	32	39	44	48

With repetition: $48 (item 1 + two of item 4). Without repetition (0/1), $K(w, j) = \max\{K(w, j-1),\ K(w - w_j, j-1) + v_j\}$:

items	2	3	4	5	6	7	8	9	10
1	0	0	0	0	30	30	30	30	30
1–2	0	14	14	14	30	30	30	44	44
1–3	0	14	16	16	30	30	30	44	46
1–4	9	14	16	23	30	30	39	44	46

0/1: $46 (items 1 and 3).

7 · Chain matrix multiplication

$$C(i, j) = \min_{i \le k < j}\{C(i, k) + C(k+1, j) + m_{i-1}\, m_k\, m_j\},\qquad C(i, i) = 0$$

$A_i$ is $m_{i-1} \times m_i$. $C(i, j)$ = cheapest cost of computing $A_i \cdots A_j$. Guess the last multiplication (split $k$). Fill by increasing length $j - i$. Answer $C(1, n)$. $\sim n^2/2$ subproblems × $O(n)$ = $O(n^3)$.

DPV: A 50×20, B 20×1, C 1×10, D 10×100, so $m = (50, 20, 1, 10, 100)$.

C(i, j)	j=1 (A)	j=2 (B)	j=3 (C)	j=4 (D)
i=1	0	1,000 (k=1)	1,500 (k=2)	7,000 (k=2)
i=2		0	200 (k=2)	3,000 (k=2)
i=3			0	1,000 (k=3)
i=4				0

Optimum 7,000 = $(A \times B) \times (C \times D)$: $1{,}000 + 1{,}000 + 50 \cdot 1 \cdot 100$. Other orders: $((AB)C)D$ = 51,500; $(A(BC))D$ = 60,200 (this is what "cheapest adjacent pair first" greedy picks); $A((BC)D)$ = 120,200; $A(B(CD))$ = 103,000.

Fill-order trap: rows top to bottom is invalid (C(1,4) reads C(2,4), which is below). Valid: by diagonal (length), or rows bottom to top.

8 · Independent set in a tree

$$\text{in}(u) = w(u) + \sum_{c \text{ child of } u} \text{out}(c), \qquad \text{out}(u) = \sum_{c} \max\{\text{in}(c), \text{out}(c)\}$$

Root the tree. in(u)/out(u) = best weight in u's subtree with u taken / not taken. Leaves: in = w, out = 0. Postorder. Answer $\max\{\text{in(root)}, \text{out(root)}\}$. $O(n)$ total. DPV's one-number form: $I(u) = \max\{1 + \sum_{\text{grandchildren}} I,\ \sum_{\text{children}} I\}$ (unit weights).

Root r. Vertex weights shown above each vertex: r 5, a 6, b 2, c 3, d 1, e 4, f 2, g 3.

u (postorder)	c	d	a	f	g	e	b	r
in(u)	3	1	6	2	3	4	2 + 5 = 7	5 + 4 + 5 = 14
out(u)	0	0	3 + 1 = 4	0	0	2 + 3 = 5	max(4, 5) = 5	max(6,4) + max(7,5) = 13

Answer 14: {r, c, d, f, g} = 5 + 3 + 1 + 2 + 3 (brute force agrees). Greedy "heaviest first" takes a (6), then e (4), and stops at 10.

9 · Weighted interval scheduling

$$\text{OPT}(k) = \max\{\text{OPT}(k-1),\ w_k + \text{OPT}(p(s_k) - 1)\},\qquad \text{OPT}(0) = 0$$

Sort by finish time. $p(s_k)$ = index of the first interval finishing after $s_k$ starts, so intervals $1..p(s_k)-1$ are exactly those compatible with $\ell_k$ that come before it. Either skip $\ell_k$ or take it. Sort + $n$ binary searches: $\Theta(n \log n)$.

interval	1	2	3	4	5	6
$(s_i, f_i)$	(0,3)	(1,5)	(4,7)	(3,8)	(2,9)	(6,10)
$w_i$	2	4	4	7	2	6
$p(s_i)$	1	1	2	2	1	3
OPT(i)	2	4	6	9	9	10

$\text{OPT}(6) = \max\{9,\ 6 + \text{OPT}(2)\} = \max\{9, 10\} = 10$: take $\ell_2, \ell_6$. Touching endpoints do not conflict ($\ell_1$ ends at 3, $\ell_4$ starts at 3).

10 · Binomial coefficients

$C(n, k) = C(n-1, k-1) + C(n-1, k)$, $C(n, 0) = C(n, n) = 1$. Fill rows $0..n$, columns $0..\min(i, k)$. $\Theta(nk)$ time and space (one row updated right to left gives $\Theta(k)$ space).

i \ j	0	1	2	3
0	1
1	1	1
2	1	2	1
3	1	3	3	1
4	1	4	6	4
5	1	5	10	10

11 · Rod cutting (CLRS) and HW4 P6

$$r(j) = \max_{1 \le i \le j}\{p_i + r(j - i)\},\qquad r(0) = 0$$

$r(j)$ = max revenue from a rod of length $j$. Guess the length $i$ of the first piece; the rest is cut optimally. $n$ subproblems × $O(n)$ = $O(n^2)$.

HW4 P6 (each cut costs $c$). $r(j)$ = max revenue minus cut costs for length $j$. Either sell the rod whole (no cut), or cut off a first piece of length $i < j$: that is one cut, and the remainder's own cuts are already charged inside $r(j - i)$.

$$r(j) = \max\Big(p_j,\ \max_{1 \le i < j}\{p_i + r(j - i) - c\}\Big),\qquad r(0) = 0$$

procedure cutRodWithCost(p[1..n], c)
r[0] = 0
for j = 1 to n:
    best = p[j]; first[j] = j            (no cut)
    for i = 1 to j − 1:
        if p[i] + r[j − i] − c > best:
            best = p[i] + r[j − i] − c; first[j] = i
    r[j] = best
return r[n]            (pieces: first[n], then repeat on n − first[n])

$O(n^2)$ time, $O(n)$ space. Correct because every cutting either has no cut or has a first piece $i$, and the cuts on the rest must be optimal for length $j - i$ (cut and paste). The subtle point: do not subtract $c$ in the no-cut case.

CLRS prices, checked against brute force over all cut sets:

length j	1	2	3	4	5	6	7	8
$p_j$	1	5	8	9	10	17	17	20
$r(j)$, c = 0	1	5	8	10	13	17	18	22
$r(j)$, c = 2	1	5	8	9	11	17	17	20

Example: $c = 2$, $j = 4$: whole = 9; 2+2 = 5 + 5 − 2 = 8; 1+3 = 1 + 8 − 2 = 7. So $r(4) = 9$ (with $c = 0$ it was 10 from 2+2).

12 · DPV exercises: clean exam answers

DPV 6.1: maximum-sum contiguous subsequence, $O(n)$

Subproblem: $M(j)$ = largest sum of a contiguous run ending exactly at position $j$ (empty run allowed, sum 0).
Recurrence: $M(j) = \max\{0,\ M(j-1) + a_j\}$: either extend the best run ending at $j-1$, or start fresh.
Base: $M(0) = 0$. Order: $j = 1..n$. Answer: $\max_j M(j)$; remember where the current run started to output it.
Time: $O(n)$, $O(1)$ extra space.

5, 15, −30, 10, −5, 40, 10 → $M$ = 5, 20, 0, 10, 5, 45, 55. Answer 55 (10, −5, 40, 10).

DPV 6.2 / HW4 P7: hotels, penalty $(300 - x)^2$

Subproblem: $P(j)$ = minimum total penalty of a trip from mile 0 that ends the day at hotel $j$ ($a_0 = 0$).
Recurrence: $P(j) = \min_{0 \le i < j}\{P(i) + (300 - (a_j - a_i))^2\}$: guess the hotel $i$ where the last day starts. prev($j$) = the minimizing $i$.
Base: $P(0) = 0$. Order: $j = 1..n$. Answer: $P(n)$; follow prev from $n$ to list the stops.
Time: $n$ subproblems × $O(n)$ = $O(n^2)$; $O(n)$ space.

Check: hotels at 200, 350, 550, 650, 900 → $P$ = 10000, 2500, 12500, 2500, 5000. Stops 350, 650, 900 (days of 350, 300, 250: $2500 + 0 + 2500 = 5000$). Brute force agrees. (DPV's original uses 200 instead of 300; same algorithm.)

DPV 6.3: Yuckdonald's

Subproblem: $P(j)$ = max profit using only locations $1..j$.
Recurrence: $P(j) = \max\{P(j-1),\ p_j + P(\text{prev}(j))\}$, where prev($j$) = the largest $i < j$ with $m_i \le m_j - k$ (0 if none). Either skip location $j$, or open there and use only locations at least $k$ miles back.
Base: $P(0) = 0$. Order: $j = 1..n$. Answer: $P(n)$.
Time: $O(n^2)$ scanning back for prev; $O(n)$ with one pointer moving forward (the $m_i$ are sorted).

Check: $m$ = 2, 4, 5, 9, 10; $p$ = 6, 8, 5, 7, 4; $k = 4$. prev = 0, 0, 0, 3, 3; $P$ = 6, 8, 8, 15, 15. Answer 15 (miles 4 and 9).

DPV 6.4: word break

Subproblem: $S(j)$ = true iff $s[1..j]$ can be split into dictionary words.
Recurrence: $S(j) = \bigvee_{0 \le i < j}\big(S(i) \wedge \text{dict}(s[i+1..j])\big)$: guess where the last word starts. Store back($j$) = an $i$ that worked.
Base: $S(0) = \text{true}$. Order: $j = 1..n$. Answer: $S(n)$. (b) If true, output words by following back from $n$: $s[\text{back}(n)+1..n]$, then repeat from back($n$).
Time: $O(n^2)$ dict calls.

Check: "itwasthebest" with dict {it, was, the, best, be, st, a, i, of, times} → $S(12)$ true, words: it | was | the | best.

DPV 6.7: longest palindromic subsequence, $O(n^2)$

Subproblem: $L(i, j)$ = length of the longest palindromic subsequence of $x[i..j]$.
Recurrence: if $x_i = x_j$ ($i < j$): $L(i, j) = 2 + L(i+1, j-1)$; else $L(i, j) = \max\{L(i+1, j),\ L(i, j-1)\}$. Guess whether the two ends are used.
Base: $L(i, i) = 1$; $L(i+1, i) = 0$ (empty). Order: increasing length $j - i$. Answer: $L(1, n)$.
Time: $O(n^2)$ entries × $O(1)$. (Alternative: LCS of $x$ and its reverse, also $O(n^2)$.)

Check: DPV's sequence A, C, G, T, G, T, C, A, A, A, A, T, C, G → 8 (e.g. C T A A A A T C). Brute force agrees.

DPV 6.8: longest common substring, $O(mn)$

Subproblem: $T(i, j)$ = length of the longest common substring ending exactly at $x_i$ and $y_j$.
Recurrence: $T(i, j) = T(i-1, j-1) + 1$ if $x_i = y_j$, else $0$ (a substring must be contiguous, so a mismatch resets it).
Base: $T(i, 0) = T(0, j) = 0$. Order: row by row. Answer: $\max_{i,j} T(i, j)$ (not the corner).
Time: $O(mn)$.

	B	A	B	C	A
–	0	0	0	0	0
A	0	1	0	0	1
B	1	0	2	0	0
A	0	2	0	0	1
B	1	0	3	0	0
C	0	0	0	4	0

x = ABABC, y = BABCA → 4 (BABC). Contrast with LCS: there the mismatch case takes a max instead of resetting to 0.

DPV 6.9: cutting a string (interval DP)

Setup: sort the cut positions $c_1 < \dots < c_m$; add $c_0 = 0$, $c_{m+1} = n$.
Subproblem: $C(i, j)$ = min cost to make all cuts strictly between $c_i$ and $c_j$ on the piece $[c_i, c_j]$.
Recurrence: $C(i, j) = (c_j - c_i) + \min_{i < k < j}\{C(i, k) + C(k, j)\}$: guess the first cut $c_k$ made on this piece; it costs the piece's length.
Base: $C(i, i+1) = 0$. Order: increasing $j - i$. Answer: $C(0, m+1)$.
Time: $O(m^2)$ subproblems × $O(m)$ = $O(m^3)$.

Check: $n = 20$, cuts 3, 10 → 30 (cut 10 first: 20 + 10), matching DPV. $n = 10$, cuts 2, 4, 7 → 20. Both confirmed by trying every cut order.

Self-check

1. Why is LIS defined as "ending exactly at j" and not "best among the first j"?

To extend a subsequence by $a_j$ you must know its last element is $< a_j$. "Ending at j" records that last element; "best among the first j" does not, so no valid recurrence exists for it. Answer is then $\max_j L(j)$, not $L(n)$.

2. In the 1-D 0/1 knapsack loop, what goes wrong if w runs upward?

$B[w - w_k]$ may already include item $k$ from this same pass, so item $k$ can be taken repeatedly. You get knapsack with repetition (DPV example: 48 instead of 46).

3. The knapsack DP is $O(nW)$ but knapsack is NP-hard. Why no contradiction?

$O(nW)$ is pseudo-polynomial: input size counts the bits of $W$, about $\log W$, so $W = 2^{\text{bits}}$ is exponential in input size.

4. Edit distance of kitten → sitting? Subproblem count and time for strings of lengths m, n?

3 (substitute k→s, substitute e→i, insert g). $(m+1)(n+1)$ subproblems, $O(1)$ each, $O(mn)$.

5. Rod cutting with cut cost $c = 2$, CLRS prices. What is $r(5)$ and which cut achieves it?

$r(5) = 11$: pieces 2 + 3 give $5 + 8 - 2 = 11$, beating the whole rod (10) and 1 + 4 ($1 + 9 - 2 = 8$).

6. Chain matrix multiplication: which fill order is invalid, and what is the running time?

Rows top to bottom ($i = 1, 2, \dots$) is invalid, since $C(i, j)$ reads $C(k+1, j)$ in a lower row. Fill by increasing length (or rows bottom to top). $O(n^2)$ subproblems × $O(n)$ splits = $O(n^3)$.