动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。

输入：n个矩阵A1,A2,…,An，其中Ai的维数为pi-1×pi Ai 和Ai+1是可乘的

输出：连乘积A1A2A3…An

优化目标：最小计算代价（最优的计算次序）

三个矩阵A1: 10×100, A2: 100×5，A3: 5×50 (A1A2)A3 代价：10×100×5＋10×5×50＝7500 A1(A2A3) 代价：100×5×50＋10×100×50＝75000

可见不同的计算次序会导致不同的计算代价，我们要做的就是让这个代价最小。

我们自然可以用穷举法计算每次不同的结合次序带来的不同代价，然后取最小值，但是这样我们得到的复杂度将达到

将矩阵连乘积AiAi+1…Aj，记为A[i:j]

设AiAi+1…Aj的最优计算次序在矩阵Ak和Ak+1之间将矩阵链断开得到：(Ai… Ak) (Ak+1 …Aj)

总的计算量就是：A[i:k]的计算量＋A[k+1: j]的计算量+A[i:k]和A[k+1:j]相乘的计算量

建立的递归关系就是

计算A[i:j]所需的最小乘法次数为m（i，j） 其中Ai是Pi-1 x Pi的矩阵

接下来我们借助填表过程理解递归的过程，现在给出下列矩阵：

填表过程是按对角线填写的，只利用到了二维数组的右上角一部分。

根据地推公式，我们可以知道，在i=j时m=0，所以先构造出最长的对角线部分的数据，如下图：

现在我们继续构造， m（1,2）=min{m[1][1]+m[2][2]+p0p1p2}={0+0+303515}=15750

m(2,3) = min(m[2][2]+m[3][3]+p1p2p3=0+0+35155）=2625

同理，后面不再一一列举；

再多说一点，有时我们会遇到有多个划分，我们取最小值就可以了，

例如：m（1,4）=min{m[1][2]+m[3][4]+p0p2p4 或者是 m[1][1]+m[2][4]+p0p1p4或者是m[1][3]+m[4][4]+p0p3p4}，其中的值已经在前面求出来了，这也是动态规划要记录所有值的原因。

结果图如下：读者可以自行计算验证。

那么，我们最后如何得知是哪个地方要加括号呢？ 根据最后的公式。

例如，假设最后的m[1:6]=m[1,1]+m[2][6]+p0p2p6（笔者构造的，跟上面的例子没关系），那么我们就知道是（A1(A2A3A4A5A6)）,再看m[2:6],根据公式找退出括号位置，一直推到最后即可。

我们不难发现，加括号的位置其实就是k 的对应序号的矩阵，在写算法时我们就可以用另外的数组记录下对应位置的k值。在最后输出时把这个数组按逻辑输出。

最终这个算法的复杂度 代码如下：(摘录自：大佬的博客中的代码)