Often students get confused what are differences between divide and conquer and dynamic programming. Since they solve problems in similar nature. Divide the problem into subproblems combine them to get solution. Here I list the differences between divide and conquer and dynamic programming in a table and also made quizzes so that you can practice questions.
Divide and Conquer
Dynamic Programming
Examples Quick Sort, Binary Search, Merge Sort
Examples Matrix Chain Multiplication, Bellman Ford for Shortest Path
Uses topdown approach to solve problems.
Uses bottomup approach to solve problems.
Partition the problem into independent subproblems.
Partition the problem into dependent subproblems.
It recomputes subproblems many times.
Dynamic programming solves the subproblems once and keep them into a table.
Test your memory
#1 Dynamic programming uses
BottomUp Approach
#2 Divide and conquer uses
TopDown Approach
BottomUp Approach
#3 Dynamic programming divides the problems into
Dependent SubProblems
Independent SubProblems
#4 Divide and conquer divides the problems into
Dependent SubProblems
Independent SubProblems
#5 Dynamic programming is used to solve the type of problems
Optimization Problems
Intractable Problems
finish
Results

Share to Your Friend
Share to Your Friend
Share to Your Friend
Be the first to commenton "Divide and Conquer and Dynamic Programming Algorithms"
I agree to my personal data being stored and used as per Privacy Policy
We use cookies to ensure that we give you the best experience on our website. If you continue to use this site we will assume that you are happy with it.OkPrivacy policy
Be the first to comment on "Divide and Conquer and Dynamic Programming Algorithms"