Dynamic Programming (ADU Feb 14)

Dynamic Programming (ADU Feb 14)

a WimpyPoint presentation owned by Mark Dettinger

Divide & Conquer and Dynamic Programming

Example Problems

Divide & Conquer Dynamic Programming
Multiplication in O(nlg 3)
Matrix Mult. in O(nlg 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

  1. Think about the structure of the problem. What are the subproblems?
  2. Recursively define the value of an optimal solution.
  3. Solve the subproblems bottom-up, i.e. smallest subproblems first, and save their solutions (in an array).
  4. 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