The paradigmatic example of a DP algorithm for me is the simple DP solution of the 0-1 knapsack problem, which, although because of NP-hardness of the general case, becomes infeasible on many easily constructed cases, actually performs pretty well on many non-artificial examples.
It's an example of what the article calls bottom-up dynamic programming, but I think it is a poor example of divide-and-conquer, because it naturally fits the following purely functional form:
h(foldr f a weights)
where weights is the problem, expressed as a list of (item, weight) pairs, and f, h and a are subfunctions. This is a pretty paradigmatic non-divide-and-conquer form in functional programming: it's a one-at-a-time iteration through the list expressing the problem
So while I think this is good article with plenty of food for thought, I reject the central claim.
I was commenting on the high-level claims of the article, not the specific algorithms the article describes. When you move from the article's example of a DP algorithm to the simple implementation I sketch of the 0-1 knapsack problem, the claim that DP is a kind of divide-and-conquer looks harder to sustain.
It's an example of what the article calls bottom-up dynamic programming, but I think it is a poor example of divide-and-conquer, because it naturally fits the following purely functional form:
h(foldr f a weights)
where weights is the problem, expressed as a list of (item, weight) pairs, and f, h and a are subfunctions. This is a pretty paradigmatic non-divide-and-conquer form in functional programming: it's a one-at-a-time iteration through the list expressing the problem
So while I think this is good article with plenty of food for thought, I reject the central claim.