Re:Dynamic Programming vs. Divide-and-Conquer (2018)
by thealig on Sunday April 25, 2021 @06:26AM
(#26931664)
The example given in the article for bottom-up DP is edit distance, unless you're referring to something I missed?
Re:Dynamic Programming vs. Divide-and-Conquer (2018)
by chalst on Monday April 26, 2021 @01:42AM
(#26939568)
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.