Week 6 Discussion Forum

Similarities between Dynamic Programming & Divide-and-Conquer

Similarities between Dynamic Programming & Divide-and-Conquer

by A.B.M Noman 192-15-2839 -
Number of replies: 0

It can be said that dynamic programming is an extension of divide-and-conquer paradigm.

They are not treated as something completely different. Because they both work by recursively breaking down a problem into two or more sub-problems of the same or related type until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.

So why do we still have different paradigm names then and why I called dynamic programming an extension. It is because dynamic programming approach may be applied to the problem only if the problem has certain restrictions or prerequisites. And after that dynamic programming extends divide-and-conquer approach with memoization or tabulation technique.

119 words