difference between dynamic programming and divide and conquer technique is

Question

What is the difference between dynamic programming and divide and conquer technique,

Comments

http://users.cis.fiu.edu/~giri/teach/5407/F07/LecX6.pdf

U can refer this....

---

in simple words can we say

greedy is fast

dynamic is slow

greedy is not always used to make out best feasible optimal solutions

and dynamic always make out best feasible optimal solution

 Am i correct ?

---

yes. in layman terms that is exactly what both are.

---

To add to answers below

Divide and Conquer splits at deterministic points like always in the middle etc, but in DP splits its input at every possible split points rather than at a prespecified point. After trying all split points it determines which is unique.

Answer 1

In divide and conquer we divide the larger problem into self similar smaller subproblems and use the answer to the subproblems to find the answer to the larger problem but in doing this we find the answer to each subproblems without checking whether we already computed the answer to that exactly same subproblem earlier. This increases the complexity in problems where all the subproblems are not unique . On the other hand dynamic programming handles this situation very smartly by storing the answers to the subproblems that it computed once. This is also called memoization. This reduces the time complexity in dynamic programming solutions but increases the space complexity.

Another notable difference is that in divide and conquer we recursively solve the larger problem by breaking it into subproblems. The recursion at its maximum depth takes up a lot of memory in the call stack which may sometimes lead to runtime error if the call stack space is exhausted. But in dynamic programming we can take separate dynamically allocated arrays to store solutions of subproblems and use it later to find solutions for larger problems.

Answer 2

In Dynamic programming, we take a problem in which the solutions of subproblems are overlapping, so we divide our main problem into many subproblems and store their solution into tabular form so that we wont need to calculate them again. By solving all subproblems we get the solution of our main problem.

In Greedy programming we don't have any overlapping solutions for any subproblems, we divide the main problem into small sub problems and solve them in greedy way ( what is best for now ), then we combine the solutions to get the final solution.

Answer 3

In divide and conquer we divide a given problem into sub problems(n number) and solve the subproblems. We may solve all the sub problems completely and combine the result as in the case of merge sort, or we may divide and solve only some  like binary search.

In dynamic programming a problem is divided into sub problems and we store the solution of each sub problems. So whenever the same subproblem occurs the result can be looked up. eg matrix chain multiplication.

Answer 4

DAC

In Divide and conq we divide the big problem into smaller problems until termination or we can say recursively until termination condition. In this technique we do not check all the possibilities, this is why it may or may not give the correct answer everytime.

Dynamic Programing

In dynamic programing we check all the possibilities(it is all most brutforce). We only calculate the value of distinct function calls and stores the value of that function calls into a table, this is why it is slow at start, after calculating all the distinct function calls dynamic programming is very fast as it just has to took the stored value from the table and puts its value rather then solving the same problem again.

Dynamic programming is useful when we have repeated function calls and worst when we have distinct function calls.

The best example to understand this concept is Fibonacci series  in DAC time complexity  is 2^n but in Dynamic programing it is  o(N) because of repeated function calls.

Comments

" In this technique we do not check all the possibilities, this is why it may or may not give the correct answer everytime. "

Can you please explain this statement ?

---

In dynamic programming we cover all the possible cases but in greedy and dac we do not cover all the possible ways.

Dynamic gives us the optimal solution when function calls are repeated where as dac and greedy gives feasible solution

---

Can u please give any reference for divide and conquer where it is mentioned that it does not cover all cases...

I thinkt  for Dynamic programming,  we should have optimal substructure and overlapping subproblem.. If in Divide and Conquer algorithm,  if we find the overlapping subproblems ,  then we can apply dynamic programming there otherwise we can't.. For example,  merge sort comes under divide and conquer approach but since it does not have overlapping subproblems . So we can't use dynamic programming there..I think Both cover all cases and give correct answers... DP and greedy both are used for optimization problems..

---

This is what i was trying to say, i had written distinct function calls instead of overlapping subproblems. If in Divide and Conquer algorithm,  if we find the overlapping subproblems ,  then we can apply dynamic programming there and if we apply DAC it solves the same problem again because of which time complexity increases. you have understood the concept correct my friend no worries :).