Difference between Dynamic Programming and Divide and Conquer

Question

What is the main difference between divide and conquer and dynamic programming? If we take an example merge sort is basically solved by divide and conquer which uses recursion . Dynamic programming is also based on recursion than why not Merge sort considered to be an example of dynamic programming?

Answer 1

So I would say that D&C is a bigger concept and DP is special kind of D&C. Specifically, when you found that your subproblems need to share some calculations of same smaller subproblem, you may not want them to calculate the same things again and again, you cache the intermediate results to speed up time, that comes the DP. So, essentially, I would way, DP is a fast version of D&C.

Answer 2

D&C is used when sub-problems are independent. Dynamic programming needed when a recursive function repeats same recursive calls.

Take fibonacci recurrence: f(n)=f(n-1)+f(n-2)

For example:

f(8) = f(7) + f(6) = ( f(6) + f(5) ) + f(6)

As you can see f(6) will be calculated twice. From the recurrence relation, obviously there are too many repeating values. It's better to memorize these values rather than calculating over and over again. Most important thing in dp is memorizing these calculated values. If you look at dp problems generally an array or a matrix is used for preventing repetitive calculations.

Comparing to dp, d&c generally divides problem into independent sub-problems and memorizing any value is not necessary.

Answer 3

The two are similar in that they both break up the problem into small problems and solve those. However, in divide and conquer, the subproblems are independent, while in dynamic programming, the subproblems are dependent. Both requiring recombining the subproblems in some way, but the distinction comes from whether or not the subproblems relate to other subproblems (of the same "level")

D&C example: Mergesort

In Mergesort, you break the sorting into a lot of little "sub-sorts", that is instead of sorting 100 items, you sort 50, then 25, etc. However, after breaking the original into (for example) 4 "sub-sorts", it doesn't matter which you do first; order is irrelevant because they are independent. All that matter is that they eventually get done. As such, each time, you get an entirely independent problem with its own right answer.

DP example: Recursive Fibonacci

Though there are sub-problems, each is directly built on top of the other. If you want the 10th digit, you have to the solve the problems building up to that (1+2, 2+3, etc) in a specific order. As such, they are not independent.