You've built DP tables. You know the formula, the base cases, the iteration order.
But have you ever looked at a finished table and wondered: “Did I really need ALL of those cells?”
That 2D table has rows and rows of numbers. Some of them matter. Most of them... well, you're about to find out.
5 items, capacity 8. Fill cells in row 3 to see how the table works.
Two ideas from this lesson show up everywhere in DP optimization:
Row dependency: If each row only reads the row directly above, you never need more than two rows. This applies to knapsack, edit distance, LCS, and most 2D DP problems.
Iteration direction: When you compress to a single row, direction determines correctness. In 0/1 knapsack, backward iteration prevents an item from being counted twice. In unbounded knapsack, you want forward iteration — same item, multiple uses.
Space optimization is not a trick. It's a consequence of understanding your recurrence's dependency pattern.