Dynamic Programming
Acknowledgements
I borrow the phrasing “what to store/how to compute” from my classroom experience at IMSc, specifically in a class taught by Venkatesh Raman. Some of the checklist is inspired by Erik Demaine’s treatment of the material in his MIT OCW course. The choice of problems is a subset of Jeff Erickson’s chapter on Dynamic Programming, and a lot of the notation is borrowed from there as well.
The dynamic programming approach to a problem involves miniaturizing the problem in a way that the pieces fit together to reveal a useful big picture --- i.e, the answer you are after. Here’s the checklist:
- What are the fragments (AKA, what do we want to store)?
- Are the fragments going to be useful (AKA, where is the final answer)?
- Do we have a kickstart (AKA, what are the base cases)?
- How do the fragments come together (AKA, how do we compute the values that we have agreed to store)?
- Can we put the pieces together without getting stuck (AKA, are the dependencies in step #4 acyclic)?
Let’s execute this checklist on a few problems: