Skip to main content

Dynamic Programming: Worked Examples

Attempt each next state before reading its derivation. These fixtures are original teaching examples; see the separate practice pages for independent problems.

Example 1: repairing an insufficient state​

Edges are s->a,a->u,s->b,b->u,u->a,a->t. Two simple paths reach u: s,a,u and s,b,u. Only the second can append a,t. Endpoint u alone therefore loses a relevant constraint. (visited set,u) preserves feasibility; the number of possible visited sets is exponential. On a DAG, the endpoint state is sufficient for longest paths because extension cannot revisit a prefix vertex.

Transfer: add a finite edge budget to walks on a cyclic graph. State must include how much budget remains; an endpoint alone cannot distinguish those futures.

Example 2: value-preserving compression can break witnesses​

One item (weight=2,value=3), capacity 4. Descending in-place updates first write value[4]=3 and point to capacity 2, then write value[2]=3. The scalar answer remains 3. A later pointer walk from 4 through 2 now appears to take the item twice. Full prefix layers distinguish the old capacity-2 state from the updated one. Ascending updates have a different bug: they already report value 6.

Transfer: explain why immutable historical predecessor records can repair the witness but can consume more than O(W) total memory.

Example 3: LIS tails and a real subsequence​

Input [3,5,6,2,4] gives tails [3] -> [3,5] -> [3,5,6] -> [2,5,6] -> [2,4,6]. The final length is 3. Endpoint 6 remembers predecessor 5, which remembers 3, giving input indices [0,1,2]. Final tails [2,4,6] are not in input order. Equal values replace under lower-bound search, so [2,2] has strict length 1. An upper-bound search would compute nondecreasing length 2.

Example 4: alignment boundaries and reconstruction​

For ab -> acb, row zero is [0,1,2,3], row a is [1,0,1,2], and row ab is [2,1,1,1]. At final cell (2,3), matching b reads (1,2); inserting c reads (1,1); matching a reaches (0,0). Alignment (a,a),(None,c),(b,b) reconstructs both strings and costs 1. For a -> b, substitution costs 1; insert/delete-only distance is 2.

Example 5: capacity semantics and counted objects​

Items [(2,3),(3,4),(4,5)], capacity 5 give best value 7 from indices 0,1. For exact weight 1 no selection exists; for at-most weight 1 the empty selection has value 0. Those bases cannot be shared blindly.

Now count unlimited coins of distinct denominations [1,2] totaling 3. Unordered combinations are {1,1,1} and {1,2}: count 2. Ordered sequences are 111,12,21: count 3. A combination DP processes denominations in outer order and capacities ascending; an ordered-sequence DP processes totals in outer order and sums over final coins. Both start count[0]=1, but their decision partitions count different objects. Duplicate denomination records must be rejected or normalized under a declared denomination contract.

Example 6: grids with obstacles and negative rewards​

A 3-by-3 right/down grid with center blocked has count rows [1,1,1], [1,0,1], [1,1,2]. Its two paths are upper/right and left/lower perimeter routes. Blocking the start changes the count to 0. On the unblocked reward grid [[-5,-2],[-3,-4]], right/down totals -11 and down/right totals -12. The maximum is -11; zero is not a valid starting value at arbitrary cells. A blocked destination is unreachable, even if rewards elsewhere are positive.

Example 7: interval and tree boundaries​

Matrices with dimensions [10,30,5,60] have two parenthesizations. Left-first costs 10*30*5 + 10*5*60 = 4500; right-first costs 30*5*60 + 10*30*60 = 27000. Tree ((0,1),2) records the winning split. For a path with vertex weights [4,10,4], tree-independent-set states rooted at 0 give leaf 2 (skip,take)=(0,4), vertex 1 (4,10), and root (10,8). The optimum selects vertex 1 for 10. Both computations combine child results, but their state boundaries and cost formulas are different.

Example 8: the closing edge changes a tour​

For costs [[0,1,4],[3,0,2],[1,5,0]], the two rooted tours cost 1+2+1=4 and 4+5+3=12. The best tour is [0,1,2,0]. Remove edge 2->0: the cheap open path still exists, but its tour is invalid; the other tour now wins at 12. Negative edges do not permit repeating cities. Checking only that every city appears somewhere is insufficient; order, unique visits, edge existence and closure all matter.

Example 9: digit bounds, leading padding and cache lifetime​

Digit sum 3 in [0,25] occurs at 3,12,21, so count is 3. For [10,25], subtract the single value 3 and obtain 2. Zero has digit sum 0 exactly once. A per-query cache may include tight states because bound and target are fixed. Reusing it after changing the bound from 25 to 9 can return stale results. Padding is harmless for digit sum but would falsely mark 7 as "containing zero" if a separate digit-occurrence task treated padded 007 as its canonical form.

Example 10: weighted scheduling and a new budget​

Jobs are A=(0,2,3), B=(2,4,3), C=(0,4,7). Earliest-finish cardinality greedy picks A,B, value 6. Weighted optimization picks C, value 7. Sort by (finish,start,ID) to get A,C,B; compatible-prefix counts are 0,0,1. DP prefix values are [0,3,7,7]: B offers 3+D(1)=6, which loses to 7.

Now assign costs A=1, B=1, C=3 with total budget 2. C is infeasible and A,B is optimal at 6. State (prefix,budget) repairs the old state; a take transition uses the compatible predecessor prefix and subtracts the job cost. This extension is the capstone.

Evidence to keep​

For each example keep the state sentence, one computed transition, boundary behavior and a changed assumption. The solutions belong after an independent practice attempt, not beside the first derivation.