Dynamic Programming (ADU Feb 14)

## Dynamic Programming (ADU Feb 14)

a WimpyPoint presentation owned by Mark Dettinger

## 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(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.

```

```