Dynamic Programming, Divide and Conquer

DOC一般适合用递归，而DP不适合。

下面一段话来自： http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf

Why did recursion work so well with divide-and-conquer? The key point is that in doc, a problem is expressed in terms of subproblems that are substantially smaller, say half the size. Because of this sharp drop in problem size, the full recursion tree has only logarithmic depth and a polynomial number of nodes.

In contrast, in a typical dynamic programming formulation, a problem is reduced to subproblems that are only slightly smaller. Thus the full recursion tree generally has polynomial depth and an exponential number of nodes. However, it turns out that most of these nodes are repeats, that there are not too many distinct subproblems among them, Efficiency is therefore obtained by explicitly enumerating the distinct subproblems and solving them in the right order.