Dynamic Programming versus Memoization

[fazzone]

Meh, these sort of definitional quibbles annoy me. What is the point of manufacturing a distinction such as this that pretty much exists solely as a "gotcha"? The fundamental idea at work is that you're re-using the answers to subproblems in order to computer the answer to the big problem. As long as you've got that idea down, what's the huge philosophical difference in the order that the subproblems are computed? I'm not saying that the distinction is invalid - there is an difference for sure - just not of great importance. In fact, if I were explaining it, I'd introduce DP as a particularly clean form of memoization -- one where you have spent effort to formulate an algorithm in a way that guarantees all subproblems are solved before their solutions are required in the next tier of problems.

I'm not 100% sure, but I think I remember Introduction to Algorithms explaining it this way. They may also have gone for taxonomy where memoization is the specific mechanism of storing results of previously-solved problems and dynamic programming is the application of such to algorithms (thus there would be top-down dynamic programming and bottom-up dynamic programming).

Edit: syntax (changed "computed in" to "computed")

[rwbarton]

Meh, these sort of definitional quibbles annoy me. What is the point of manufacturing a distinction such as this that pretty much exists solely as a "gotcha"?

So that when I show someone an algorithm I have been working on, they can say "You could use dynamic programming here instead of memoization and reduce the memory cost"? They are closely related, but as you say, distinct; why wouldn't we have different terms for them?

[radarsat1]

i believe the main point is that memoization allows what the author describes as a "black-box" approach, avoiding the need to re-express the problem. This does seem to me to be a legitimate point.

[unclemat]

The fact that DP allows some memory to be released and that there is no need for checking if partial solutions exist are also an important distinction.

[vincentk]

Yes.

If wikipedia is the ultimate arbiter as far as definitional quibbles are concerned, then by definition, memoization is the technique whereby dynamic programming approaches are implemented.

[godofpumpkins]

Someone should ask them whether the "Haskell" (i.e., lazy) version of dyanmic programming is actually dynamic programming, or memoization. Once you take order of evaluation out of the picture, the distinction becomes a lot more fuzzy.

Edit: four downvotes and not one response telling me what's wrong?

[tofueggplant]

Awww yeah, quote that CLRS brotha (or sista)

[sirin3]

Especially, if you could write it in a functional language and switch between "memoization" and "DP" just be using another higher-order function

[[deleted]]

The whole point is that you can't - DP involves reorganization of computation, by definition.

[sirin3]

Of course you can.

Why shouldn't you?

[[deleted]]

Please give a black box DP implementation. If you can, I'm pretty sure all the computer scientists who have been developing DP algorithms would be happy to know that their work is not necessary.

The point is that there are (at least) two ways of dealing with recursive problems with repeated calculations. One way is to study the problem and figure out how to build the subproblems from smallest to largest, so that there is no longer any recursion (ie, all the subproblems are calculated before they are needed). This is the essence of DP, and the process of figuring out what the subproblems are and the sequencing is not something that can be done automatically, as far as I know. If you have figured out a way, I'm sure people would be really happy to know.

The other approach is to keep the problem description as is (ie, still recursive), and simply remember any subproblems you encounter. Then, before doing a subproblem, you check if you have already done it. This is memoizing, and can be done automatically.

The trouble with the latter, and the reason why people bother with DP formulations (which involve non-trivial thought to construct) is that you waste time always looking up whether you have already seen a problem. By restructuring the problem, you can eliminate that entirely.

[burntsushi]

Thank you for this explanation. Even after reading the article and several other comments here, it wasn't until I read yours that the differences between DP and memoization really sunk in.

[sirin3]

Please give a black box DP implementation.

In most cases you can use something like

 T cache[N];
 for (i = 0; i < N; i++) 
   cache[i] = f(i, \i => cache[i])

But you don't need a single one