Difference between Divide and Conquer Algo and Dynamic Programming

Question

What is the difference between Divide and Conquer Algorithms and Dynamic Programming Algorithms  How are the two terms different  I do not understand the difference between them   Please take a simple example to explain any difference between the two and on what ground they seem to be similar

User · Answer

I think of Divide  amp  Conquer as an recursive approach and Dynamic Programming as table filling    For example  Merge Sort is a Divide  amp  Conquer algorithm  as in each step  you split the array into two halves  recursively call Merge Sort upon the two halves and then merge them    Knapsack is a Dynamic Programming algorithm as you are filling a table representing optimal solutions to subproblems of the overall knapsack  Each entry in the table corresponds to the maximum value you can carry in a bag of weight w given items 1-j

User · Answer

Divide and Conquer  Divide and Conquer works by dividing the problem into sub-problems  conquer each sub-problem recursively and combine these solutions   Dynamic Programming  Dynamic Programming is a technique for solving problems with overlapping subproblems  Each sub-problem is solved only once and the result of each sub-problem is stored in a table   generally implemented as an array or a hash table  for future references  These sub-solutions may be used to obtain the original solution and the technique of storing the sub-problem solutions is known as memoization   You may think of DP   recursion   re-use  A classic example to understand the difference would be to see both these approaches towards obtaining the nth fibonacci number  Check this material from MIT     Divide and Conquer approach   Dynamic Programming Approach

User · Answer

Dynamic Programming and Divide-and-Conquer Similarities As I see it for now I can say that dynamic programming is an extension of divide and conquer paradigm  I would not treat them 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  Let   s go step by step    Dynamic Programming Prerequisites Restrictions As we   ve just discovered there are two key attributes that divide and conquer problem must have in order for dynamic programming to be applicable   Optimal substructure     optimal solution can be constructed from optimal solutions of its subproblems  Overlapping sub-problems     problem can be broken down into subproblems which are reused several times or a recursive algorithm for the problem solves the same subproblem over and over rather than always generating new subproblems   Once these two conditions are met we can say that this divide and conquer problem may be solved using dynamic programming approach  Dynamic Programming Extension for Divide and Conquer Dynamic programming approach extends divide and conquer approach with two techniques  memoization and tabulation  that both have a purpose of storing and re-using sub-problems solutions that may drastically improve performance  For example naive recursive implementation of Fibonacci function has time complexity of O 2 n  where DP solution doing the same with only O n  time  Memoization  top-down cache filling  refers to the technique of caching and reusing previously computed results  The memoized fib function would thus look like this  memFib n        if  mem n  is undefined          if  n  lt  2  result   n         else result   memFib n-2    memFib n-1                   mem n    result     return mem n     Tabulation  bottom-up cache filling  is similar but focuses on filling the entries of the cache  Computing the values in the cache is easiest done iteratively  The tabulation version of fib would look like this  tabFib n        mem 0    0     mem 1    1     for i   2   n         mem i    mem i-2    mem i-1      return mem n     You may read more about memoization and tabulation comparison here  The main idea you should grasp here is that because our divide and conquer problem has overlapping sub-problems the caching of sub-problem solutions becomes possible and thus memoization tabulation step up onto the scene  So What the Difference Between DP and DC After All Since we   re now familiar with DP prerequisites and its methodologies we   re ready to put all that was mentioned above into one picture   If you want to see code examples you may take a look at more detailed explanation here where you ll find two algorithm examples  Binary Search and Minimum Edit Distance  Levenshtein Distance  that are illustrating the difference between DP and DC

User · Answer

Divide and Conquer  In this problem is solved in following three steps  1  Divide - Dividing into number of sub-problems 2  Conquer - Conquering by solving sub-problems recursively 3  Combine - Combining sub-problem solutions to get original problem s solution Recursive approach Top Down technique Example  Merge Sort  Dynamic Programming  In this the problem is solved in following steps  1  Defining structure of optimal solution 2  Defines value of optimal solutions repeatedly  3  Obtaining values of optimal solution in bottom-up fashion 4  Getting final optimal solution from obtained values Non-Recursive Bottom Up Technique Example  Strassen s Matrix Multiplication

User · Answer

I assume you have already read Wikipedia and other academic resources on this  so I won t recycle any of that information  I must also caveat that I am not a computer science expert by any means  but I ll share my two cents on my understanding of these topics     Dynamic Programming  Breaks the problem down into discrete subproblems  The recursive algorithm for the Fibonacci sequence is an example of Dynamic Programming  because it solves for fib n  by first solving for fib n-1   In order to solve the original problem  it solves a different problem   Divide and Conquer  These algorithms typically solve similar pieces of the problem  and then put them together at the end  Mergesort is a classic example of divide and conquer  The main difference between this example and the Fibonacci example is that in a mergesort  the division can  theoretically  be arbitrary  and no matter how you slice it up  you are still merging and sorting  The same amount of work has to be done to mergesort the array  no matter how you divide it up  Solving for fib 52  requires more steps than solving for fib 2

User · Answer

The other difference between divide and conquer and dynamic programming could be   Divide and conquer    Does more work on the sub-problems and hence has more time consumption  In divide and conquer the sub-problems are independent of each other    Dynamic programming    Solves the sub-problems only once and then stores it in the table  In dynamic programming the sub-problem are not independent

User · Answer

Divide and Conquer  They broke into non-overlapping sub-problems Example  factorial numbers i e  fact n    n fact n-1     fact 5    5  fact 4    5    4   fact 3    5   4    3  fact 2    5   4   3   2    fact 1    As we can see above  no fact x  is repeated so factorial has non overlapping problems   Dynamic Programming  They Broke into overlapping sub-problems Example  Fibonacci numbers i e  fib n    fib n-1    fib n-2     fib 5    fib 4    fib 3     fib 3  fib 2      fib 2  fib 1    As we can see above  fib 4  and fib 3  both use fib 2   similarly so many fib x  gets repeated  that s why Fibonacci has overlapping sub-problems   As a result of the repetition of sub-problem in DP  we can keep such results in a table and save computation effort  this is called as memoization

User · Answer

sometimes when programming recursivly  you call the function with the same parameters multiple times which is unnecassary   The famous example Fibonacci numbers               index  1 2 3 4 5 6    Fibonacci number  1 1 2 3 5 8     function F n        if  n  lt  3          return 1     else         return F n-1    F n-2      Let s run F 5    F 5    F 4    F 3          F 3  F 2      F 2  F 1            F 2  F 1   1     1 1         1 1 1 1 1   So we have called   1 times F 4  2 times F 3  3 times F 2  2 times F 1   Dynamic Programming approach  if you call a function with the same parameter more than once  save the result into a variable to directly access it on next time  The iterative way   if  n  1    n  2      return 1 else     f1 1  f2 1     for i 3 to n          f   f1   f2          f1   f2          f2   f   Let s call F 5  again   fibo1   1 fibo2   1  fibo3    fibo1   fibo2    1   1   2 fibo4    fibo2   fibo3    1   2   3 fibo5    fibo3   fibo4    2   3   5   As you can see  whenever you need the multiple call you just access the corresponding variable to get the value instead of recalculating it   By the way  dynamic programming doesn t mean to convert a recursive code into an iterative code  You can also save the subresults into a variable if you want a recursive code  In this case the technique is called memoization  For our example it looks like this      declare and initialize a dictionary var dict   new Dictionary lt int int gt     for i 1 to n     dict i    -1  function F n        if  n  lt  3          return 1     else               if  dict n     -1              dict n    F n-1    F n-2           return dict n                            So the relationship to the Divide and Conquer is that D amp D algorithms rely on recursion  And some versions of them has this  multiple function call with the same parameter issue   Search for  matrix chain multiplication  and  longest common subsequence  for such examples where DP is needed to improve the T n  of D amp D algo

User · Answer

Divide and Conquer involves three steps at each level of recursion    Divide the problem into subproblems  Conquer the subproblems by solving them recursively  Combine the solution for subproblems into the solution for original problem    It is a top-down approach  It does more work on subproblems and hence has more time consumption  eg  n-th term of Fibonacci series can be computed in O 2 n  time complexity      Dynamic Programming involves the following four steps      1  Characterise the structure of optimal solutions    2  Recursively define the values of optimal solutions   3  Compute the value of optimal solutions   4  Construct an Optimal Solution from computed information    It is a Bottom-up approach  Less time consumption than divide and conquer since we make use of the values computed earlier  rather than computing again  eg  n-th term of Fibonacci series can be computed in O n  time complexity      For easier understanding  lets see divide and conquer as a brute force solution and its optimisation as dynamic programming   N B  divide and conquer algorithms with overlapping subproblems can only be optimised with dp

[algorithm] Difference between Divide and Conquer Algo and Dynamic Programming

Examples related to algorithm

Examples related to dynamic-programming

Examples related to divide-and-conquer