本文主要讲解了动态规划中的矩阵链乘问题：给定一个矩阵链，得到它的最小代价计算次序。给出了动态规划方案的分析，并且给出了C语言实现。

给定一个n个矩阵的序列（矩阵链） < A 1 , A 2 , A 3 , A 4 , . . . , A n > ，现在我们希望计算它的乘积 A 1 A 2 A 3 A 4 . . . A n A_1 A_2A_3A_4...A_n A1​A2​A3​A4​...An​ 对于矩阵链乘来说，我们可以通过加括号的手段来确定先让哪两个矩阵进行相乘。无论乘的次序如何，最终都不影响结果。 但是不同次序之间的矩阵相乘，计算机所要付出的代价完全不一样。 比如所 < A 1 , A 2 , A 3 > , 其中 A 1 为 2 ∗ 3 ； A 2 为 3 ∗ 4 ； A 3 为 4 ∗ 1 ,其中A_1为2*3；A_2为3*4；A_3为4*1 ,其中A1​为2∗3；A2​为3∗4；A3​为4∗1 我们可以计算两种不同策略的切割代价：

显然，两种代价是完全不一样的。现在我们的问题就是给定一个矩阵链，得到它的最小代价计算次序。

我们先直接给出相应的递归求解公式： w [ i , j ] = { 0  if  i = j m i n { w [ i , k ] + w [ k + 1 , j ] + p i − 1 p k p j }  if  i < j w[i,j]=\begin{cases} 0& \text{ if }i=j \\ min\{ w[i,k]+w[k+1,j]+p_{i-1}p_kp_j\}& \text{ if } i