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 sub-problems 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|
Quick Sort, Binary Search, Merge Sort
|Examples- Matrix Chain Multiplication, Bellman Ford for Shortest Path|
|Uses top-down approach to solve problems.||Uses bottom-up approach to solve problems.|
|Partition the problem into independent sub-problems.||Partition the problem into dependent sub-problems.|
|It recomputes sub-problems many times.||Dynamic programming solves the sub-problems|
once and keep them into a table.
Test your memory
#1 Dynamic programming uses
#2 Divide and conquer uses
#3 Dynamic programming divides the problems into
#4 Divide and conquer divides the problems into
#5 Dynamic programming is used to solve the type of problems