Dynamic Programming

Cool name for a cheap trick. Dynamic programming is based on recursion and memoizes (stores) the results. Recursion can be used if a problem can be broken down into parts. If you think of quick sort or merge sort, these are great examples. If each part doesn’t overlap, then recursion is simple and you get your answer. The issue can be stickier if the calculations overlap. Fibonacci series is a great example of problem overlap. Assume you want to know what the Fibonacci value is at the 27^th step. It would be the sum of the 25^th and 26^th steps. But how much are those? If you consider the 26^th, it is the 24^th and 25^th. But wait a moment. We need the 25^th to solve the 27^th. We can’t split this problem in half without overlap. Both halves want to know what the 25^th step is. Answer? Memoize or store it. Have a common cache that maps the step to the value. One side finds out the 25^th before the other one, fine. Store it, and the second process pulls it from the cache. 25^th is only solved once.

Like I said, cool name for a cheap trick