Algorithms from zero
Dynamic programming: free-recall review
Retrieval beats re-reading. For each prompt, say or write a full answer from memory before you open the model answer — the effort of recall is what makes the material stick.
Reconstruct the unit’s spine — the two enabling properties, memoization vs tabulation, how to design a state and its transition, and how space optimization works — without looking back at the lessons.
- 01What two properties must a problem have before dynamic programming applies, and what does each one buy you?
- 02Contrast memoization and tabulation. When would you pick each?
- 03How do you design the state for a DP problem, and what makes a state correct?
- 04What is a transition, and why must the iteration order respect it?
- 05Explain how space optimization (the rolling array) works and when it is safe.
- 06Take Longest Increasing Subsequence: give the O(n^2) DP, the O(n log n) idea, and the trap in the fast version.
If you could reconstruct each answer from memory, you hold the unit’s spine: confirm overlapping subproblems and optimal substructure, choose memoization or tabulation by stack depth and space needs (not big-O), design the minimal sufficient state, write a transition over every choice and iterate in an order that respects it, and roll the table down to a window only when no still-needed value is overwritten. Same complexity either way — states times work per state.