Dynamic programming is similar to divide-and-conquer, it divide the original problem into small part, but they have different directions, Dynamic programming is bottom-up, while divide-and-conquer is a top-down approach. In this approach, we solve the small instance and store the result in a table, when we need the result, we just search in the table, and thus save large amount of time to re-calculation.

The steps in the development of a dynamic programming algorithm are as follows:

1. Establish a recursive property that gives the solution to an instance of the problem.

2. Solve an instance of the problem in a bottom-up fashion by solving smaller instances first.

A famous applications of dynamic programming is Floyd's Algorithm for Shortest Paths.

Using dynamic programming, we create a cubic-time algorithm for the Shortest Paths problem. First we develop an algorithm that determines only the lengths of the shortest paths. After that we modify it to produce shortest paths as well. We represent a weighted graph containing n vertices by an array W where

The array D in Figure 3.3 contains the lengths of the shortest paths in the graph. For example, D[3][5] is 7 because 7 is the length of a shortest path from v₃ to v₅. If we can develop a way to calculate the values in D from those in W, we will have an algorithm for the Shortest Paths problem. We accomplish this by creating a sequence of n + 1 arrays D^(k), where 0 ≤ k ≤ n and where

• D^(k)[i][j] = length of a shortest path from v_i to v_j using only vertices in the set {v₁, v₂, …, v_k} as intermediate vertices.

Therefore, to determine D from W we need only find a way to obtain D⁽ⁿ⁾ from D⁽⁰⁾. The steps for using dynamic programming to accomplish this are as follows:

Dynamic programming algorithm provides a solution for an optimization problem, and the steps in the development of such an algorithm are as follows:

1. Establish a recursive property that gives the optimal solution to an instance of the problem.

2. Compute the value of an optimal solution in a bottom-up fashion.

3. Construct an optimal solution in a bottom-up fashion.

Steps 2 and 3 are ordinarily accomplished at about the same point in the algorithm.

The principle of optimality is said to apply in a problem if an optimal solution to an instance of a problem always contains optimal solutions to all substances.