动态规划与分治法的异同：

相同点：其基本思想都是将待求解问题分解为若干子问题，先求解子问题，再结合这些子问题的解得到原问题的解。

差异点：与分治法不同的是，适合用动态规划法求解的问题经分解得到的子问题往往不是相互独立的。有些问题分解后的子问题往往是重复的，此时若用分支法则会重复计算耗费时间内存。

总结：为了达到避免重复计算，可以用一个表来记录所有已解决的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。

步骤：

矩阵连乘问题

动态规划算法的基本要素

最优子结构：当问题的最优解包含了其子问 题的最优解时，称该问题具有最优子结构性质。

重叠子问题：在用递归算法自顶向下解此问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算。动态规划算法对每个子问题只解一次，然后将解保存在一个表格中。

问题描述：

给定n个矩阵：A1,A2,…,An，其中Ai与Ai+1是可乘的，i=1，2…，n-1。确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。输入数据为矩阵个数和每个矩阵规模，输出结果为计算矩阵连乘积的计算次序和最少数乘次数。

问题解析：

由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。

例如，矩阵连乘积A1A2A3A4有5种不同的完全加括号的方式：(A1(A2(A3A4)))，(A1((A2A3)A4))，((A1A2)(A3A4))，((A1(A2A3))A4)，(((A1A2)A3)A4)。每一种完全加括号的方式对应于一个矩阵连乘积的计算次序，这决定着作乘积所需要的计算量。

有点需要记住，两个矩阵相乘之后得到的矩阵的行为前面一个矩阵的行，列为后面一个矩阵的列，复杂度与第一个矩阵的列也有关。

递推规律：

设计算A[i:j]（矩阵A从i乘到j），1≤i≤j≤n，所需要的最少数乘次数m[i,j]，则原问题的最优值为m[1,n]（上面例题就是m[1][6]）。

  当i=j时，A[i:j]=Ai，因此，m[i][i]=0，i=1,2,…,n   当i