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 |
|---|---|
| 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. |
| Examples- Quick Sort, Binary Search, Merge Sort | Examples- Matrix Chain Multiplication, Bellman Ford for Shortest Path |
Test your memory
[HDquiz quiz = "376"]