Algorithms from zero
Dynamic programming: build and prove a DP solver
Reading about DP is not the same as deriving one under pressure. Pick a real optimization problem, take it from naive recursion all the way to a space-optimized table, and prove every step is correct — the loop you run in every interview and every real solver.
Turn the unit’s checklist into a reproducible engineering loop: name the state, write the transition, memoize it, convert to tabulation, optimize space, reconstruct the path, and verify the whole thing against an independent brute-force oracle.
Implement one non-trivial DP problem end to end — edit distance, 0/1 knapsack, or weighted interval scheduling — taking it from a brute-force baseline through memoization, tabulation, and a space-optimized version, with the optimal solution path reconstructed and every stage validated against an independent oracle.
- A randomized differential test runs at least 1000 small cases comparing memoized, tabulated, and space-optimized solvers against the brute-force oracle; all agree on the optimal value.
- The reconstructed path is validated: re-applying it (e.g. replaying the edit script, summing the chosen items' weights and values) reproduces the optimal value within the stated constraints.
- A short table lists each version's time and space complexity with a one-line justification, and the space-optimized version provably uses asymptotically less memory than the full table.
- A one-paragraph write-up names the state and transition in plain words and explains why the chosen iteration order is correct (every read precedes its write).
- Add a second problem from a different state shape (e.g. an interval-DP problem such as matrix-chain or burst balloons) and reuse the same oracle harness to validate it.
- Instrument the memoized version to count cache hits vs misses and the brute force to count total calls; plot how the gap grows with input size to make the exponential-to-polynomial collapse concrete.
- Handle the pseudo-polynomial trap: for knapsack, show how the O(n*W) table blows up as capacity W grows even with few items, and discuss when a meet-in-the-middle or approximation is needed instead.
- Generalize the reconstruction into a reusable trace utility that, given a filled dp table and the transition, returns the optimal path for any of your solvers.
This is the loop you will run on every DP, in interviews and in production solvers: write the recurrence before any code, build a brute-force oracle you trust, then climb memoization to tabulation to a space-optimized window, re-verifying against the oracle at each step, and finally reconstruct the path — not just the value. Doing it once on a toy problem makes the next one muscle memory: name the state, write the transition, prove the order, optimize last.