Tricki

## When exhaustive search takes too long and a greedy algorithm is not optimal, consider Dynamic Programming

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

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).

At termination, contains the weights of the minimal weight paths of length between any pair of vertices. Determining the actual paths is done in a similar manner, essentially replacing with argmin in (1). This algorithm runs in time and space.

### General discussion

Remark The recurrence relation (1) is just matrix multiplication formula over the semiring (sometimes called the tropical semiring). This implies that over that semiring.