A note on Dynamic Programming

This is a quick note about Dynamic Programming from The Algorithm Design Manual book. I found it really helpful.

Why dynamic programming is so hard?

• Until you understand dynamic programming, it seems like magic.
• You must figure out the trick before you can use it.

The trick

• 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.

The advice on how to learn

• Dynamic programming is best learned by carefully studying examples until things start to click