Week 6 Discussion Forum

What is the difference between dynamic programming and divide and conquer?

What is the difference between dynamic programming and divide and conquer?

by Tawhid Ahmed Komol 192-15-2861 -
Number of replies: 1

In both the approaches you divide a problem into smaller subproblems, solve them and combine their results to solve the bigger problem. This breaking up of the problem into subproblems can be several levels deep.

The difference between the two lies in the nature of subproblems. In divide and conquer paradigm, all subproblems are independent in nature and they do not overlap when you keep dividing problems into subproblems, each subproblem is required to be solved only once.

While in dynamic programming a subproblem solved as part of one bigger subproblem may be required to be solved again as part of another subproblem, so the very first time a subproblem is solved it's results are tabulated(stored in some efficient datastructure) and the next time it is encountered instead of solving it again, the result is simply looked up in the table and returned.


144 words

In reply to Tawhid Ahmed Komol 192-15-2861

Re: What is the difference between dynamic programming and divide and conquer?

by Sajia Afrin 192-15-2907 -
/*/Divide and Conquer
//In Divide and Conquer 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 Dynamic Programming 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: DP coin change problem

97 words