Section 5 of 5 · Algorithms & Data Structures
Dynamic Programming, Proof & Transfer
Dynamic programming tests whether a problem state contains exactly the information the future needs. Deriving that state and proving the recurrence transfers directly to batching, caching and resource allocation.
9 units 18 topics 0/9
Units
9 in this section
- 5.1 Dynamic programming states, transitions and base cases derive3 h
- 5.2 Memoization, tabulation and dependency order implement3 h
- 5.3 Solution reconstruction and rolling state implement3 h
- 5.4 Sequence and string dynamic programming derive · implement4 h
- 5.5 Grid, path and interval dynamic programming derive · implement4 h
- 5.6 Tree dynamic programming derive · implement3 h
- 5.7 Knapsack, subset and bitmask dynamic programming derive · implement4 h
- 5.8 Recurrence proofs and differential validation derive · measure3 h
- 5.9 Dynamic programming as shortest paths, formulations and limits explain · derive4 h
Before moving on
Checkpoint
Derive and implement two tag-hidden dynamic programs from blank files, reconstruct a witness, and repair one subtly wrong recurrence using a minimized counterexample.
Deliberately out of scope
Leave for later
- Specialized dynamic-programming optimizations
- NP-hardness reductions and advanced approximation
- Competitive-programming trick catalogs
Resources for this section
Shared by every unit above
- DSA Handbook - dynamic programming Study Part 9 in order from state and recurrence through sequence, grid, tree and bitmask families. For every example, close the page and reconstruct the state, transition and evaluation order.
- AlgoMaster DSA - dynamic programming slice Attempt Coin Change, Longest Common Subsequence and House Robber III cold. Write the state, transition, base case and evaluation order first; compare against brute force on small inputs and reconstruct a witness when available.
- Algorithms - dynamic programming Use the dynamic-programming chapter to derive states and recurrences from first principles and to separate DP from greedy reasoning and shortest paths.
- Hypothesis - exhaustive and differential DP tests Generate small valid instances, compare memoized, tabulated and exhaustive results, and retain shrunk failures for wrong state, base case, order and compression defects.
- NeetCode - unseen mixed problems Use two tag-hidden mixed problems as the final transfer test. One must require rejecting a tempting greedy or insufficient-state solution with a counterexample.
- Python sys: recursion limit Read
sys.getrecursionlimitandsys.setrecursionlimit: the limit guards the C stack and its safe maximum is platform-dependent. Check the default withgetrecursionlimit(1000 on CPython 3.13), raise it once for memoized DP, or switch to tabulation for deep inputs. - Erickson lecture note D - Advanced Dynamic Programming Read Section D.1 (Saving Space: Divide and Conquer) for the Hirschberg Half-table split that recovers an optimal edit sequence in \(O(m + n)\) space.
- Erickson lecture note J - Approximation Algorithms Read Section J.1 (Load Balancing) for the Partition reduction that makes exact scheduling NP-hard, the
GreedyLoadBalanceheuristic, and Theorem J.1 with its factor-2 proof.
Apply the section
Mini-project · Two tag-hidden schedules with witnesses and a repaired recurrence (10 to 14 h)
Derive two scheduling dynamic programs from blank files, each returning a witness for an independent checker. A differential harness shrinks, pins and repairs one subtly wrong recurrence, training the formulation judgment the capstone needs.
Steps
- Solve LC 983 Minimum Cost For Tickets with tags hidden: write the subproblem specification, recurrence, base case and evaluation order before code. Return the cost with a witness of the passes bought.
- Build the harness: Hypothesis generates small inputs and compares memoized, tabulated and brute-force answers, while a checker validates that each witness covers every travel day at exactly the reported total.
- Plant an off-by-one in the pass coverage, let Hypothesis shrink a failure, pin it with
@exampleand repair the recurrence. Map the shrunk input to the exact claim the planted recurrence made. - Solve LC 1335 Minimum Difficulty of a Job Schedule with tags hidden, with a state over the first unscheduled job and days left that returns its cut points as a witness. Differential-test against brute force over all cut positions on small inputs.
- Prove both recurrences by induction: name the case split, why the state is sufficient, and why no invalid schedule is admitted.
- Write a transfer note for each problem: the smallest sufficient state and one smaller state that fails, with a counterexample.
Deliverables
- Both solutions with specifications, witnesses and an independent witness checker.
- The Hypothesis harness with the pinned failure, the planted recurrence and its repair.
- The proofs and transfer notes for both problems.
Checks
- rubric · Self-grade with the rubric below
- external-tests · LeetCode 983: Minimum Cost For Tickets
- external-tests · LeetCode 1335: Minimum Difficulty of a Job Schedule
Rubric
| Criterion | Pass | Strong |
|---|---|---|
| Recurrence formulation | Specification, recurrence, base cases and order are written before code for both problems. | Each transfer note refutes a smaller state with a concrete counterexample. |
| Witness reconstruction | Both solutions return witnesses that an independent checker validates. | The witness checker runs inside the Hypothesis harness on every example. |
| Harness and repair | Memoized, tabulated and brute-force answers agree on generated examples, while the planted recurrence fails with its shrunk input pinned and the repair passing. | The write-up maps the shrunk input to the exact claim the planted recurrence made. |
| Inductive proof | One recurrence is proved by induction with its case split named. | Both are proved, including why no invalid schedule is admitted. |
Feeds into: Capstone correctness library: one reconstructing DP. Failure evidence: the planted recurrence and its repair. Transfer: two tag-hidden scheduling problems.