Quick description
Dynamic programming is a "smart exhaust," and is often used to find examples in the case where a greedy algorithm does not return an optimal result. In this article, we describe the criteria needed for a problem to posses a dynamic programming (DP) solution. We also give the general algorithm.
Prerequisites
None
Example 1
The basic example of a problem which admits a DP solution is that of finding minimal weight paths of a fixed length between vertices of a weighted, undirected graph on vertices . If we write the weight between vertex and as , we can collect the weights into a matrix . Let denote the minimal weight path of length starting at vertex and ending at vertex . Then we have the recurrence
Here we have written path weight additively. This suggests an algorithm to determine the minimal weight paths between any two vertices:

Initialize

for do

Determine by (1).

Comments
What is a "smart exhaust"?
Mon, 15/06/2009  23:44 — Sharon (not verified)What is a "smart exhaust"?