Dynamic Programming
To solve a complex problem by:
- Breaking it down into a collection of simpler sub-problems; smallest first
- Solving each of those sub-problems just once;
- Storing their solutions - ideally using a memory-based data structure.
Divide and conquer
1. Divide/Break
This step involves breaking the problem into smaller sub-problems. Sub-problems should represent as a part of original problem. This step generally takes recursive approach to divide the problem until no sub-problem is further dividable. At this stage, sub-problems become atomic in nature but still represents some part of actual problem.
2. Conquer/Solve
This step receives lot of smaller sub-problem to be solved. Generally at this level, problems are considered 'solved' on their own.
3. Merge/Combine
When the smaller sub-problems are solved, this stage recursively combines them until they formulate solution of the original problem.
This algorithmic approach works recursively and conquer & merge steps works so close that they appear as one.
Examples
The following computer algorithms are based on divide-and-conquer programming approach
- Merge Sort
- Quick Sort
- Binary Search
- Strassen's Matrix Multiplication
- Closest pair (points)
Greedy Algorithm:
- treats the solution as some sequence of steps and picks the locally optimal choice at each step, but it doesn't guarantee the global optimal solution.