Week 6 Discussion Forum

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

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

by Sajia Afrin 192-15-2907 -
Number of replies: 0
/*/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