This is a quick note about Dynamic Programming from The Algorithm Design Manual book. I found it really helpful.
- Until you understand dynamic programming, it seems like magic.
- You must figure out the trick before you can use it.
- Dynamic Programming is a technique for efficiently implementing a recursive algorithm by storing partial results.
- The trick is: seeing whether the naive recursive algorithm computes the same subproblems over and over again.
- If so, storing the answer for each subproblem in a table to lookup instead of recomputing.
- Start with a recursive algorithm or definition. Only once we have a correct recursive algorithm, do we worry about speeding it up by using a result matrix.
- Dynamic programming is best learned by carefully studying examples until things start to click