FREE Algorithms LESSON · Algorithms
Turn repetition into state
Dynamic programming, graphs, and state compression
Dynamic programming is a graph calculation in disguise.
A recursive problem defines states and dependencies between states. Dynamic programming becomes possible when different paths reach the same state and the result of that state can be reused. The hard work is not writing a cache: it is choosing the smallest state that preserves every fact the future needs, proving the recurrence, identifying base cases, and selecting an evaluation order that respects dependencies.
Memoization is an implementation technique. The intellectual move is discovering a sufficient state and a valid recurrence.
A smaller table can encode a larger mistake.
State compression is valid only when discarded history cannot change any future transition or payoff. Rolling arrays often work because one row depends on a fixed number of prior rows; they fail when reconstruction needs older choices or when a hidden dependency reaches farther back. Compare full and compressed formulations on adversarial small cases before trusting the memory win.
Compress a proven recurrence, not an intuition about which values seem old.