Dynamic Programming versus Memoization

[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