Developing a Dynamic Programming algorithm

Dynamic Programming (ADU Feb 14)

Dynamic Programming (ADU Feb 14)

a WimpyPoint presentation owned by Mark Dettinger

Divide & Conquer and Dynamic Programming
Developing a Dynamic Programming algorithm

Divide & Conquer and Dynamic Programming

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.

Example Problems

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

Developing a Dynamic Programming 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