Build solutions from a written recurrence
Solve coin change, nonadjacent rewards, and longest common subsequence. Before coding, write each state's meaning, base cases, transition, evaluation order, and result location.
Use these fixtures:
Coin change: coins [1,3,4], amount 6 -> 2
Coin change: coins [2], amount 3 -> unreachable
Nonadjacent rewards: [2,7,9,3,1] -> 12
LCS: "abcde", "ace" -> 3
LCS: "abc", "xyz" -> 0
First implement a slow exhaustive solver for tiny inputs. Use it as an oracle to validate the optimized DP across seeded random cases. Then compress memory only after the full table is correct, documenting which old values must survive each update.
Acceptance checks
Test empty input, impossible states, repeated values, ties, and numeric bounds. Add reconstruction of one actual solution, not just its score, and verify that it obeys the original constraints.
Check: an optimal score alone can hide a broken reconstruction. If multiple optima exist, define deterministic tie-breaking or test validity and score without demanding one arbitrary sequence.