**Divide & Conquer**and**Dynamic Programming**are two strategies that solve problems by solving subproblems and combining their solutions.- Divide & Conquer is good when the subproblems are independent.
- Dynamic Programming is better when the subproblems share common subsubproblems.

Divide & Conquer | Dynamic Programming |
---|---|

Quicksort
Mergesort Multiplication in O(n ^{lg 3})
Matrix Mult. in O(n ^{lg 7})
| |

Fibonacci Numbers
Binomial Coefficients The Coin Change Problem Longest Common Subsequence Shortest Common Supersequence Edit Distance Matrix Chain Multiplication Polygon Triangulation Floyd-Warshall Algorithm |

- Think about the structure of the problem. What are the subproblems?
- Recursively define the value of an optimal solution.
- Solve the subproblems bottom-up, i.e. smallest subproblems first, and save their solutions (in an array).
- Now you know the value of the optimal solution. To compute the solution itself, extend your algorithm in the appropriate way.

*Last modified 2001-02-14*

mdettinger@arsdigita.com |