In calculating the optimal order of multiplying m matrices

where matrix M_i has dimension n_i × n_i + 1, we use a dynamic program which calculates the optimal order of calculating M_i × ··· × M_j where first j = i + 1, then j = i + 2, etc.

In the case when j = i + 1, the cost of multiplying M_i × M_i + 1 is simply n_i n_i + 1 n_i + 2.

In the case where j = i + 2, the cost of multiplying M_i × M_i + 1 × M_i + 2 is the lesser of the cost of multiplying (M_i × M_i + 1) × M_i + 2 and M_i × (M_i + 1 × M_i + 2).

Two source codes are provided: an easier variation of the algorithm which simply calculates the cost involved and one which indicates the order of the multiplications.