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

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

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

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

步骤：

矩阵连乘问题

动态规划算法的基本要素

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

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

问题描述：

给定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 //矩阵链中只有一个矩阵时，次数为0，注意m[0][X]时未使用的 m[i][i]=0; } for(int r=2;r //根据链长度，控制链最大的可起始点 int j = i+(r-1); //矩阵链的末尾矩阵，注意r-1，因为矩阵链为2时，实际是往右+1 m[i][j] = m[i][i]+m[i+1][j]+p[i-1]*p[i]*p[j]; //先设置最好的划分方法就是直接右边开刀，后续改正，也可合并到下面的for循环中 s[i][j]=i; for(int k=i+1;k m[i][j] = t; s[i][j] = k; } } } } } /* *追踪函数：根据输入的i,j限定需要获取的矩阵链的始末位置，s存储断链点 */ void Traceback(int i,int j, int s[][N]){ if(i==j) //回归条件 { cout int p[N]={30,35,15,5,10,20,25}; int m[N][N],s[N][N]; MatrixChain(p,N-1,m,s);//N-1因为只有六个矩阵 Traceback(1,6,s); return 0; }

运行结果：

备忘录方法：

代码如下：

运行结果：