Contents
ToggleDynamic programming
Dynamic programming is used to solve many problems from operational research, which is why we will not list the tutorials related to this method.
Dynamic Programming is an exact method of problem solving
optimization, mainly due to R. Bellman (1957).
More specifically, dynamic programming is an algorithm design paradigm that one can apply to solve a problem if it meets Bellman optimality.
Dynamic programming is similar in idea to the method divide and rule. The significant difference between these two methods is that dynamic programming allows subproblems to overlap. In other words, a subproblem can be used in the solution of two different subproblems. While the divide and conquer approach creates separate subproblems that can be solved independently of each other.
The fundamental difference between these two methods is therefore: the subproblems in dynamic programming can be interacting, while in the divide and rule method they are not.
A second difference between these two methods is, as illustrated by the figure above, is that the divide and reign method is recursive, the recursion takes the global problem to split it into an elementary problem. Dynamic programming is a method whose calculations are done from the bottom up: we start by solving the smallest subproblems. By combining their solution, we obtain the solutions of increasingly large subproblems.
Principle
The paradigm breaks down into four issues:
 Characterization of the structure of an optimal solution.
 Recursive definition of the value of the optimal solution.
 Ascending calculation of the solution.
 Construction of the solution from the ascending calculation.
We build a table to memorize the calculations already carried out: to each element will correspond the solution of one and only one intermediate problem, and one for the final solution. It is therefore necessary that one can determine the subproblems which will be treated during computation.
There are two approaches to populating the table:
 Iterative: We initialize the “boxes” corresponding to the base cases.
One then fills the table according to a very precise order to be determined: one starts with the problems of “size” as small as possible, one finishes with the solution of the main problem: it is necessary that for each computation, one uses only the solutions already calculated.  Recursive: Same principle as the iterative approach, this method will only calculate what is strictly necessary to achieve the given objective.
Example: product of matrices
Be not matrices M_{1}, …, M_{not}, each matrix has a number m_{i} of lines and m_{i + 1} columns, the entries are real numbers (linear problem). We seek to calculate M_{1}*…*M_{not} so as to minimize the number of operations.
We denote by c_{ij} the number of operations to calculate M_{i}*…*M_{j}. We then have c_{ii}= 0 and c_{i (i + 1)}= m_{(i1)}* m_{i}* m_{(i + 1)} operations. Let us split this subproblem by calculating the best c_{ij} with M_{i}*…*M_{k} and M_{(k + 1)}*…*M_{j}. So_{ij} = min [c_{ik} + c_{(k + 1) j} + m_{i}* m_{(k + 1)}* m_{(d + 1)}] with k of i To d1, the last term amounts to multiplying the results of the product of matrices of i To k with that of k + 1 To j.
So we have the following program:
 vs_{ij} = 0 if i = j;
 vs_{i (i + 1)}= m_{(i1)}* m_{i}* m_{(i + 1)};
 vs_{ij} = min [c_{ik} + c_{(k + 1) j} + m_{i}* m_{(k + 1)}* m_{(d + 1)}] otherwise.
The table of the dynamic program takes as input the number of operations carried out according to the chosen matrices. Consider the following example:
i

1

2

3

4

5

6

7

m_{i}

30

35

15

5

10

20

25

The initial table is as follows:
vs_{ij}

1

2

3

4

5

6

1

0

–

–  –  –  – 
2

–  0  –  –  –  – 
3

–  –  0  –  –  – 
4

–  –  –  0  –  – 
5

–  –  –  –  0  – 
6

–  –  –  –  –  0 
Then we can calculate c_{ij} with two matrices (without principle of substructure):
vs_{ij}

1

2

3

4

5

6

1

0

15750

–  –  –  – 
2

–  0  2625  –  –  – 
3

–  –  0  750  –  – 
4

–  –  –  0  1000  – 
5

–  –  –  –  0  5000 
6

–  –  –  –  0 
The rest of the table is filled diagonal by diagonal according to the rule described above:
vs_{ij}

1

2

3

4

5

6

1

0

15750

7875  9375  11875  15125 
2

–  0  2625  4375  7125  10500 
3

–  –  0  750  2500  5375 
4

–  –  –  0  1000  3500 
5

–  –  –  –  0  5000 
6

–  –  –  –  –  0 
The result is obtained for i = 1 and j = 6, ie the box at the top right of the table. The minimum cost is therefore 15125 operations. A new question then arises: how did we proceed to have a minimum number of calculations?
When we calculate the minimum cost for each box, we choose from two configurations. For example to calculate c_{13}, we take the minimum between c_{12}* M_{3} and M_{1}*vs_{23}. It suffices to note the choice made in order to know the order of calculation of the matrix product.
K_{ij}

1

2

3

4

5

6

1

–

–

1  3  3  3 
2

–  –  –  3  3  3 
3

–  –  –  –  3  3 
4

–  –  –  –  –  5 
5

–  –  –  –  –  – 
6

–  –  –  –  –  – 
The table reads as follows: to calculate M_{i}* M_{j}, we set k = K_{ij} given by the table then we calculate M_{i}*…*M_{k} and M_{(k + 1)}*…*M_{j} which is then multiplied together.
In our example, to calculate vs_{16}, we calculate c_{13}*vs_{46}; to calculate vs_{13}, we calculate M_{1}*vs_{23}; to calculate vs_{46} we calculate c_{45}* M_{6}.
Most of algorithm based on dynamic programming retains in memory the choice made for each calculation. Often the result is not important, the journey to achieve it is.
Example: currency exchange
We want to change the change on £ 67. For this we want to use the minimum number of pieces of type: 1, 5, 10, 25.
Here it is easy to guess the optimal solution 67=2*25+10+5+2*1. By always choosing the coin with the highest possible value, we obtain a solution (by greedy algorithm).
The problem is written as follows: Let D={ d_{1}, .., d_{k}} a finite number of coin value. It is assumed that each d_{i }is an integer and the set is sorted by increasing value. Each coin value is available unlimited. The problem is to make the change on a value of n£ with a minimum number of coins, if d_{k} = 1 then there is always a solution.
The greedy method does not always give an optimal solution. For example, D = {25,10,1} and n = 30. The optimal method will give the following solution: 25 + 5 * 1, which is worse than 3 * 10.
Step 1: Characterize the optimal substructure. Let us define C [j] as the optimal solution for the sum j £. We can thus remove a part and thus find an optimal solution for C [j] = 1 + C [jdi].
Step 2: Value of the optimal solution. We can recursively define the optimal solution from the substructure.
Step 3: Algorithm.
CoinChanging (n, d, k) C [0] = 0; For j from 1 to n C [j] = inf; For i from 1 to k If j> = di and C [jdi] <C[j] then C[j]=1+C[jdi] Denom[j]=di Return C
We use an additional table called Denom, such that Denom[j] represents the piece to use to obtain an optimal solution for a sum j£. If we go up Denom by the value of the coin until we reach j=1, then we know the coin selection that has been made. Let's take the example with the following coins: 1, 5, 10, 25:
j  0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15 
C [j]  0  1  2  3  4  1  2  3  4  5  1  2  3  4  5  2 
Denom [j]  0  1  1  1  1  5  1  1  1  1  10  1  1  1  1  5 
From an amount n£, we can find all the coin combinations allowing to make the change. Let's take the same coin values: 1, 5, 10, 25. For example, for N=4, D={1,2,3} there are four solutions: {1,1,1,1}, {1 ,1,2}, {2,2} and {1,3}.
Step 1: Optimal substructure, C (N, m) can be partition one two sets:
 Solutions containing no parts_{m}
 solutions containing at least one piece of_{m}
If a solution does not contain part of_{m}, then we can solve the subproblem of N with D = {d_{1}, .., d_{m1}}, that is to say the solutions of C (N, m1).
If a solution contains d_{m}, then we are going to remove a piece of_{m}, we must therefore solve the subproblem N d_{m} , with D = {d_{1}, .., d_{m}}. Let solve the following problem C (N d_{m}, m).
2nd step: The rule is: C (Nm) = + C (N d_{m}, m) with the basic conditions:
 C (N, m) = 1, N = 0
 C (N, m) = 0, N <0
 C (N, m) = 0, N> = 1, m <= 0
Step 3: The solutions of the algorithm are reported in a table of the form
n / a  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15 
1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 
5  1  1  1  1  2  2  2  2  2  3  3  3  3  3  4 
10  1  1  1  1  2  2  2  2  2  4  4  4  4  4  6 
25  1  1  1  1  2  2  2  2  2  4  4  4  4  4  6 