Dynamic Programming: Case Studies
These are synthetic engineering scenarios, not verified company incidents. Each asks for a model, a counterexample and a reviewable decision.
Case 1: the planner with a new budget
A weighted single-resource scheduler starts returning over-budget plans after
costs are added to jobs. Filtering the old chosen plan afterward can discard
the true affordable optimum. Derive (prefix,budget) state and use the
capstone fixture. Deliver before/after contracts, a take/skip
proof and tests that validate time compatibility and cost independently.
Case 2: the memory-saving packer
A team rolls a 0/1 knapsack table into one capacity array. Values still match
the full version, but some selected-ID lists repeat an item. Reproduce with
one (2,3) item and capacity 4. Explain mutable predecessor versions, propose
a reconstruction strategy and report its actual storage. Do not describe the
value-only O(W) bound as the full artifact's bound without evidence.
Case 3: the text comparison service
A proposed exact alignment feature accepts arbitrary 100,000-character pairs. Estimate ten billion cell evaluations and the full-table payload before benchmarking. Specify tokenization, operation costs and whether a full alignment is required. Compare a bounded-input exact contract with a threshold/banded alternative, stating what proof or guarantee makes pruning safe. Do not silently label an approximate or restricted result as unrestricted Levenshtein distance.
Case 4: counting IDs with a digit property
A counter includes zero and uses leading padding for fixed-length processing. The requirement changes from digit sum to "contains a zero digit". Explain why padded 007 must not make integer 7 qualify. Define canonical zero behavior, augment the state and compare a fresh small range to enumeration. Review cache lifetime when several bounds are queried in one process.
Case 5: the tiny tour planner that grew
A subset tour solver works on eight stops and is proposed for thirty. Estimate state slots and transitions, including parents, before making a feasibility claim. Clarify missing roads, direction, repeat visits and whether an exact tour is required. Offer a measured input limit or a separately specified alternative; neither NP-hardness nor a successful tiny benchmark settles all practical instances.
For each case retain assumptions, the smallest separating example, chosen design, verification evidence and untested limits. Score changed-assumption reasoning with the competency rubric, not the realism of the story.