DP & greedy problem clinic (design on a novel problem)

The DP recipe you apply to ANY new problem

The exam and the OilKnapsack project both want you to design a DP, not recall one. Always the same four steps:

1. Characterize the structure of an optimal solution — what's the last/first choice, and what subproblem remains after it? Prove optimal substructure by cut-and-paste (a better subsolution would let you improve OPT — contradiction).
2. Define the recurrence — write the optimal value as a max/min over the choices, in terms of smaller subproblems. Include base cases.
3. Compute bottom-up (or top-down + memo) — fill a table in an order that has every dependency ready. Running time = (#subproblems) × (work per subproblem).
4. Reconstruct the solution — store the choice made at each cell (not just the value) and walk it back.

Worked design 1 — edit distance (a novel DP)

Problem: minimum insert/delete/substitute operations to turn string $s$ into $t$. Subproblem: $D[i][j]$ = edit distance between the prefixes $s[\mathrm{1..}i]$ and $t[\mathrm{1..}j]$. Recurrence:

$$D[i][j]=\{\begin{array}{ll}i& j=0\\ j& i=0\\ D[i-1][j-1]& s_i=t_j\\ 1+\min (D[i-1][j],D[i][j-1],D[i-1][j-1])& \text{else}\end{array}$$

The three inner options are delete $s_i$, insert $t_j$, substitute. Base cases: turning a prefix into the empty string costs its length. Time Θ(mn), space Θ(mn) (or Θ(min(m,n)) keeping two rows). This is the shape of almost every string-DP exam question.

Worked design 2 — weighted interval scheduling (where greedy fails)

Activity selection (Module 5) is greedy: pick the earliest-finishing compatible activity. But if each job has a weight and you want maximum total weight, greedy-by-finish is wrong — a single heavy job can beat several light ones. This is the canonical 'greedy fails, use DP' problem.

Sort jobs by finish time. Let $p(i)$ = the largest index $j<i$ with ${\text{finish}}_j\le {\text{start}}_i$ (the last compatible job). Subproblem: $M[i]$ = max weight using jobs $\mathrm{1..}i$. Recurrence:

$$M[i]=\max (\underset{\text{skip }i}{\underbrace{M[i-1]}},\underset{\text{take }i}{\underbrace{w_i+M[p(i)]}}),M[0]=0.$$

The exercise below computes an instance where the DP scores 17 but greedy-by-finish only 16 — the concrete proof that weight breaks greedy.

The greedy exchange-argument template

When greedy does work (activity selection, Huffman, Kruskal, Prim), prove it with an exchange argument: take any optimal solution OPT; show you can swap OPT's first choice for the greedy choice without making it worse (equal or better); repeat, transforming OPT into the greedy solution while preserving optimality. This proves the greedy-choice property — that a globally optimal solution contains the greedy first choice.