4 ms·
The example given in the article for bottom-up DP is edit distance, unless you're referring to something I missed?
by thealig 5y ago
The example given in the article for bottom-up DP is edit distance, unless you're referring to something I missed?
- chalst 5y agoI 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.
- thealig 5y agoYes, agreed. The examples seem fine to me as far as DP is concerned, but the claim of divide and conquer is a bit weird