[zestyping]

Thanks for helping clear this up.

It seems that many dynamic programming solutions can be arrived at by starting with a recursive formulation, adding memoization, and then optimizing the cache based on specialized knowledge of the problem. For example:

1. Q: How can you compute Fibonacci number f(n) recursively? A: f(n) = f(n-1) + f(n-2)

2. Q: How can you memoize the results of your recursive function(s) to dramatically reduce the number of calls? A: Make a cache keyed on n that stores f(n).

3. Q: Given specialized understanding of the problem, how can you minimize the size of the cache? A: Notice that you don't need to keep all O(n) slots; you only need to keep two ints.

Can every dynamic programming solution be explained this way? Or is there a good example of a dynamic programming problem for which you really need to make a leap that can't be sensibly reached through this sequence of three questions?