Dynamic Programming

Solving a problem by solving its smaller subproblems first and reusing the answers. Every technique here is the same idea seen from a different angle: write the recurrence, cache the overlapping calls, then turn the recursion inside-out into a table - and finally shrink the table to the handful of cells you actually need.

The progression we repeat on every problem:

• LRU Cache - the bare recurrence with @lru_cache doing the memoization for free.
• Memoization - the same top-down recursion with an explicit dp array, so the caching is visible.
• Tabulation, O(n) space - the recursion turned bottom-up; the call stack becomes a loop over the dp table.
• Tabulation, O(k) space - the table kept to only the last k cells the recurrence reads, via modular indexing.