算法分析矩阵连乘

矩阵连乘问题的算法
一、矩阵连乘问题
矩阵连乘问题是指在矩阵计算中，给定n个矩阵，求这n个矩阵的连乘积的最优解问题。

矩阵连乘问题既可以用于组合优化，也可以用于信息处理系统中查找最优路径的搜索算法。

它是最基本的组合优化问题。

二、矩阵连乘问题的算法
1. 动态规划法：动态规划法是求解矩阵连乘问题的常用算法。

它采用递归方法，将原问题分解为若干个子问题，然后求出各子问题的最优解，最后组合出原问题的最优解。

2. 贪心算法：贪心算法是一种经典的最优化算法，也可以用于求解矩阵连乘问题，即通过某种启发式规则，在每一步中都使最优决策，最终得到最优解。

3. 分支定界法：分支定界法是一种由搜索算法和界定法相结合而成的最优化算法，也可以用于求解矩阵连乘问题。

该算法按照树状的层次结构，向下搜索一个在每一步骤都使得当前最优的路径，然后上溯形成最优解。

4. 模拟退火算法：模拟退火算法是一种搜索算法，它可以用于求解矩阵连乘问题。

它采用一种模拟物理过程的原理，通过不断地改变解的状态，以求出相对最优解。

- 1 -。

矩阵连乘问题（动态规划算法）动态规划算法思想简介：将⼀个问题分解为多个⼦问题，这点和分治法类似，但是每个⼦问题不是独⽴的⽽是相互联系的，所以我们在求解每个⼦问题的时候可能需要重复计算到其他的⼦问题，所以我们将计算过的⼦问题的解放进⼀个表中，这样就能避免了重复计算带来的耗费，这就是动态规划的基本思想；⼀般地，动态规划思想⼀般⽤来解最优化问题，主要分为以下四个步骤：（1）找出最优解的性质，并刻画其结构特征；（2）递归地定义最优值；（3）以⾃底向上的⽅式计算出最优值；（4）根据计算得到的最优值时得到的信息，构造最优解；同时，问题的最优⼦结构性质也是该问题可⽤动态规划算法求解的显著特征，这⾥的最优⼦结构性质即指：问题的最优解也即代表着它的⼦问题有了最优解；问题描述：分析过程如下：（1）分析最优⼦结构的性质：（2）分析递归关系，以及利⽤⾃底向上的⽅式进⾏计算：（3）获取最优值和最优解：代码如下：#ifndef MATRIX_CHAIN_H#define MATRIX_CHAIN_Hvoid matrix_chain(int *p, int n, int **m, int **s);void traceback(int i, int j, int **s);#endif#include <iostream>#include "matrix_chain.h"using namespace std;//利⽤动态规划算法获取最优值void matrix_chain(int *p, int n, int **m, int **s) //p:各个矩阵的列数，n：矩阵个数，m：m[i:j]矩阵i到j的相乘次数，s:对应的分开位置{for (int i = 0; i < n; i++){m[i][i] = 0;}for (int r = 2; r <= n; r++){for (int i = 0; i < n - r + 1; i++){int j = i + r - 1;m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j];s[i][j] = i;for (int k = i + 1; k < j; k++){int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];if (t < m[i][j]){m[i][j] = t;s[i][j] = k;}}}}}//利⽤s[i][j]获取最优解void traceback(int i, int j, int **s){if (i == j)return;traceback(i, s[i][j], s);traceback(s[i][j] + 1, j, s);cout << "Multiply A" << i << " , " << s[i][j];cout << "and A" << (s[i][j] + 1) << " , " << j << endl;}#include <iostream>#include "matrix_chain.h"using namespace std;int main(void){int matrix_num = 0; //矩阵个数cout << "请输⼊矩阵个数：" << endl;cin >> matrix_num;int **m = new int *[matrix_num];for (int i = 0; i < matrix_num; i++)m[i] = new int[matrix_num];int **s = new int *[matrix_num];for (int i = 0; i < matrix_num; i++)s[i] = new int[matrix_num];int *p = new int[matrix_num];cout << "请输⼊各矩阵的列数：" << endl;for (int i = 0; i < matrix_num; i++){cin >> p[i];}matrix_chain(p, matrix_num, m, s);traceback(0, matrix_num - 1, s);system("pause");return1;}可结合我的另⼀篇关于贪⼼算法的博客进⾏⽐较，了解这两者的区别；。

word设计性实验报告课程名称：《算法分析与设计》实验题目：矩阵连乘问题组长：成员一：成员二：成员三：系别：数学与计算机科学系专业班级：指导教师：实验日期：一、实验目的和要求实验目的熟悉动态规划算法设计思想和设计步骤，掌握基本的程序设计方法，培养学生用计算机解决实际问题的能力。

实验要求1、根据实验内容，认真编写源程序代码、上机调试程序，书写实验报告。

2、本实验项目考察学生对教材中核心知识的掌握程度和解决实际问题的能力。

3、实验项目可以采用集中与分散实验相结合的方式进行，学生利用平时实验课时间和课外时间进行实验，要求在学期末形成完整的项目程序设计报告。

二、实验内容提要矩阵连乘问题给定n个矩阵{A1,A2,…,A n}，其中，Ai与Ai+1是可乘的，i=1,2，…，n-1。

考查这n 个矩阵的连乘积A1,A2,…,A n。

由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。

这种计算次序可以用加括号的方式来确定。

若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。

完全加括号的矩阵连乘积可递归地定义为：（1）单个矩阵是完全加括号的；（2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=（BC）。

三、实验步骤下面考虑矩阵连乘积的最优计算次序问题的动态规划方法。

（1）分析最优解的结构（最优子结构性质）设计求解具体问题的动态规划算法的第一步是刻画该问题的最优解结构特征。

对于矩阵乘积的最优计算次序问题也不例外。

首先，为方便起见，降矩阵乘积Ai Ai+1…Aj简记为A[i:j]。

考查计算A[1：n]的最优计算次序。

设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，1<=k<n,则其相应的完全加括号方式为（（A1…Ak）（Ak+1…An））即依此次序，先计算A[1：k]和A[k+1：n]，然后将计算结果相乘得到A[1：n]。

算法设计与分析——矩阵连乘问题（动态规划）⼀、问题描述引出问题之前我们先来复习⼀下矩阵乘积的标准算法。

int ra,ca;//矩阵A的⾏数和列数int rb,cb;//矩阵B的⾏数和列数void matrixMultiply(){for(int i=0;i<ra;i++){for(int j=0;j<cb;j++){int sun=0;for(int k=0;k<=ca;k++){sum+=a[i][k]*b[k][j];}c[i][j]=sum;}}}给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。

如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。

例如，给定三个连乘矩阵{A1，A2，A3}的维数分别是10*100，100*5和5*50，采⽤（A1A2）A3，乘法次数为10*100*5+10*5*50=7500次，⽽采⽤A1（A2A3），乘法次数为100*5*50+10*100*50=75000次乘法，显然，最好的次序是（A1A2)A3，乘法次数为7500次。

加括号的⽅式对计算量有很⼤的影响，于是⾃然地提出矩阵连乘的最优计算次序问题，即对于给定的相继n个矩阵，如何确定矩阵连乘的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。

⼆、问题分析矩阵连乘也是Catalan数的⼀个常⽤的例⼦，关于时间复杂度的推算需要参考离散数学关于Catalan的内容。

下⾯考虑使⽤动态规划法解矩阵连乘积的最优计算次序问题。

1、分析最优解的结构问题的最优⼦结构性质是该问题可以⽤动态规划求解的显著特征！！！2、建⽴递归关系3、计算最优值public static void matrixChain(int n) {for (int i = 1; i <= n; i++) {m[i][i] = 0;}for (int r = 2; r <= n; r++) {//i与j的差值for (int i = 1; i <= n - r + 1; i++) {int j = i + r - 1;m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j];s[i][j] = i;for (int k = i + 1; k < j; k++) {int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];if (t < m[i][j]) {m[i][j] = t;s[i][j] = k;}}}}}4、构造最优解public static void traceback(int i, int j) {if (i == j) {System.out.printf("A%d", i); // 输出是第⼏个数据return;}System.out.printf("(");traceback(i, s[i][j]);// 递归下⼀个数据System.out.printf(" x ");traceback(s[i][j] + 1, j);System.out.printf(")");}三、总结。

福州大学数学与计算机科学学院《计算机算法设计与分析》上机实验报告（2）i<=k<j,则：m[i][j]=m[i][k]+m[k+1][j]+pi-1pkpj。

由于在计算是并不知道断开点k的位置，所以k还未定。

不过k的位置只有j-i个可能。

因此，k是这j-i个位置使计算量达到最小的那个位置。

综上，有递推关系如下：若将对应m[i][j]的断开位置k记为s[i][j]，在计算出最优值m[i][j]后，可递归地由s[i][j]构造出相应的最优解。

s[i][j]中的数表明，计算矩阵链A[i:j]的最佳方式应在矩阵Ak和Ak+1之间断开，即最优的加括号方式应为(A[i:k])(A[k+1:j)。

从s[1][n]记录的信息可知计算A[1:n]的最优加括号方式为(A[1:s[1][n]])(A[s[1][n]+1:n])，进一步递推，A[1:s[1][n]]的最优加括号方式为(A[1:s[1][s[1][n]]])(A[s[1][s[1][n]]+1:s[1][s[1][n]]] )。

同理可以确定A[s[1][n]+1:n]的最优加括号方式在s[s[1][n]+1][n]处断开...照此递推下去，最终可以确定A[1:n]的最优完全加括号方式，及构造出问题的一个最优解。

3、动态规划迭代算法设计：用动态规划迭代方式解决此问题，可依据其递归式自底向上的方式进行计算。

在计算过程中，保存已解决的子问题的答案。

每个子问题只计算一次，而在后面需要时只需简单检查一下，从而避免了大量的重复计算，最终得到多项式时间的算法。

4、算法代码：1.//3d1-2 矩阵连乘动态规划迭代实现2.//A1 30*35 A2 35*15 A3 15*5 A4 5*10 A5 10*20 A6 20*253.//p[0-6]={30,35,15,5,10,20,25}4.#include "stdafx.h"5.#include <iostream>ing namespace std;7.8.const int L = 7;9.10.int MatrixChain(int n,int **m,int **s,int *p);11.void Traceback(int i,int j,int **s);//构造最优解12.13.int main()14.{15.int p[L]={30,35,15,5,10,20,25};16.17.int **s = new int *[L];18.int **m = new int *[L];19.for(int i=0;i<L;i++)20. {21. s[i] = new int[L];22. m[i] = new int[L];23. }24.25. cout<<"矩阵的最少计算次数为："<<MatrixChain(6,m,s,p)<<endl;26. cout<<"矩阵最优计算次序为："<<endl;27. Traceback(1,6,s);28.return 0;29.}30.31.int MatrixChain(int n,int **m,int **s,int *p)32.{33.for(int i=1; i<=n; i++)34. {35. m[i][i] = 0;36. }37.for(int r=2; r<=n; r++) //r为当前计算的链长（子问题规模）38. {39.for(int i=1; i<=n-r+1; i++)//n-r+1为最后一个r链的前边界40. {41.int j = i+r-1;//计算前边界为r，链长为r的链的后边界42.43. m[i][j] = m[i+1][j] + p[i-1]*p[i]*p[j];//将链ij划分为A(i) * ( A[i+1:j] )44.45. s[i][j] = i;46.47.for(int k=i+1; k<j; k++)48. {49.//将链ij划分为( A[i:k] )* (A[k+1:j])50.int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];51.if(t<m[i][j])52. {53. m[i][j] = t;54. s[i][j] = k;55. }56. }57. }58. }59.return m[1][L-1];60.}61.62.void Traceback(int i,int j,int **s)63.{64.if(i==j) return;65. Traceback(i,s[i][j],s);66. Traceback(s[i][j]+1,j,s);67. cout<<"Multiply A"<<i<<","<<s[i][j];68. cout<<" and A"<<(s[i][j]+1)<<","<<j<<endl;69.}上述迭代算法的运行过程如下图所示：当R=2时，先迭代计算出： m[1:2]=m[1:1]+m[2:2}+p[0]*p[1]*p[2]；m[2:3]=m[2:2]+m[3:3]+p[1]*p[2]*p[3];。

一、实验背景与目的矩阵连乘问题是一个经典的算法问题，它涉及给定一系列矩阵，确定这些矩阵的最佳乘积顺序，以最小化乘法操作的次数。

本实验旨在通过动态规划算法解决矩阵连乘问题，加深对动态规划方法的理解，并提高算法分析与设计的能力。

二、实验内容与步骤1. 问题描述与理解：- 给定n个矩阵A1, A2, ..., An，其中任意两个相邻矩阵都是可乘的。

- 目标是确定计算这些矩阵连乘积的最佳顺序，以最小化所需的乘法次数。

2. 算法分析：- 使用动态规划方法，通过将问题分解为子问题并存储子问题的解来求解。

- 设定m[i, j]表示矩阵Ai到Aj的最佳乘积顺序的乘法次数。

3. 动态规划过程：- 初始化m[i, i] = 0，因为单个矩阵不需要乘法。

- 对于长度为k的矩阵序列，通过遍历所有可能的分割点，计算m[i, j]的最小值。

- 具体步骤包括：- 对于每个可能的k（1 ≤ k ≤ n-1），- 对于每个起始矩阵i（1 ≤ i ≤ n-k），- 计算m[i, i+k-1]和m[i+k, j]，- 更新m[i, j]为m[i, i+k-1] + m[i+k, j] + p[i-1] p[i] p[i+k]。

4. 代码实现：- 使用C或Java等编程语言实现动态规划算法。

- 编写辅助函数来计算矩阵的乘法次数。

三、实验结果与分析1. 实验结果：- 通过实验，成功实现了矩阵连乘问题的动态规划算法。

- 得到了计算给定矩阵序列连乘积所需的最小乘法次数。

2. 结果分析：- 动态规划方法有效地解决了矩阵连乘问题，避免了穷举法的指数级时间复杂度。

- 通过分析子问题的解，我们可以找到整个问题的最优解。

四、实验总结与反思1. 实验收获：- 加深了对动态规划方法的理解，特别是如何通过子问题的解来构建整个问题的解。

- 学会了如何将实际问题转化为动态规划问题，并使用代码实现算法。

2. 反思与展望：- 实验过程中遇到了一些挑战，如理解子问题的定义和计算最优子结构的策略。

一、矩阵连乘（动态规划、备忘录）1、矩阵连乘给定n个矩阵{A1，A2，…，An}，其中Ai与Ai+1可乘的，i=1,2，…，n-1。

找出这个n个矩阵的连乘A1A2…An所需相乘的最少次数的方式。

2、分析矩阵连乘满足结合律，且不同的结合方式，所需计算的次数不同。

利用备忘录方法，用表格保存以解决的子问题答案，降低重复计算，提高效率。

m初始化为0，表示相应的子问题还位被计算。

在调用LookupChain时，若m[i][j]>0，则表示其中储存的是所要求子问题的计算结果，直接返回此结果即刻。

否则与直接递归算法一样，自顶而下的递归计算，并将计算结果存入m[i][j]后返回。

因此，LookupChain总能返回正确的值，但仅在它第一次被调用时计算，以后调用就直接返回计算结果。

用MemorizedMatrixChain函数将已经计算的数据存入表中，用LookupChain函数配合MemorizedMatrixChain函数递归调用计算。

但是备忘录方法记录了计算过程产生的值，从而不重复计算，被计算了的值，把时间的复杂度从2的n次方降低到n的3次方。

3、伪代码int MemoizedMatrixChain(int number_used){for(int i=1;i<=number_used;i++){for(int j=i;j<=number_used;j++) m[i][j]=0;}return LookupChain(1,number_used);}int LookupChain(int i,int j){if(m[i][j]>0) return m[i][j];if(i==j) return 0;int u=LookupChain(i,i)+LookupChain(i+1,j)+p[i-1]*p[i]*p[j];s[i][j]=i;for(int k=i+1;k<j;k++){int t=LookupChain(i,k)+LookupChain(k+1,j)+p[i-1]*p[k]*p[j];if(t<u) {u=t;s[i][j]=k;}}m[i][j]=u;return u;}void Traceback(int i,int j){if (i == j){cout << "A" << i;}else{cout << "(";Traceback(i,s[i][j]);Traceback(s[i][j]+1,j);cout << ")";}}4、程序实现#include <iostream>using namespace std;const int MAX = 50;class matrix{public:int p[MAX];int m[MAX][MAX];int s[MAX][MAX];int number_used;void input();int LookupChain(int i,int j);void Traceback(int i,int j);matrix();};matrix::matrix(){for(int i=0;i<MAX;i++){p[i]=0;for(int j=0;j<MAX;j++){m[i][j]=0;s[i][j]=0;}}cout<<"input the matrix number: ";cin>>number_used;input();cout<<"output the result："<<endl;LookupChain(1,number_used);Traceback(1,number_used);cout<<endl;}void matrix::input(){cout<<"the matrix: ";cout<<endl<<"input the row of A1 and columns of Ai: ";for(int j=0;j<=number_used;j++){cin>>p[j];}}int matrix::LookupChain(int i,int j){if(i==j) return 0;if(m[i][j]>0) return m[i][j];int u=LookupChain(i,i)+LookupChain(i+1,j)+p[i-1]*p[i]*p[j];s[i][j]=i;for(int k=i+1;k<j;k++){int t=LookupChain(i,k)+LookupChain(k+1,j)+p[i-1]*p[k]*p[j];if(t<u) {u=t;s[i][j]=k;}}m[i][j]=u;return u;}void matrix::Traceback(int i,int j) {if (i == j){cout << "A" << i;}else{cout << "(";Traceback(i,s[i][j]);Traceback(s[i][j]+1,j);cout << ")";}};int main(){matrix m;return 0;}运行情况：。

矩阵连乘问题的算法介绍矩阵连乘问题是一个经典的数学问题，它涉及到如何寻找一组矩阵相乘的最优顺序，使得计算所需的乘法操作总数最小化。

这个问题在计算机科学和算法设计中有着重要的应用。

本文将介绍矩阵连乘问题的算法及其相关概念和应用。

问题描述给定一组矩阵{A1, A2, A3, …, An}，其中Ai的维度为pi-1 × pi（1 ≤ i ≤ n），我们希望找到一种矩阵相乘的顺序，使得计算这些矩阵相乘所需的乘法操作总数最小化。

动态规划算法动态规划算法是解决矩阵连乘问题的经典方法。

它通过存储中间结果来避免重复计算，从而提高计算效率。

下面将介绍动态规划算法的具体实现步骤。

定义子问题假设我们要计算矩阵Ai × Ai+1 × … × Aj的最优顺序和乘法操作总数，其中i ≤ j。

确定状态转移方程设m[i][j]表示计算矩阵Ai × Ai+1 × … × Aj的最优顺序和乘法操作总数。

根据定义，我们有以下状态转移方程： - 当i = j时，m[i][j] = 0，因为只有一个矩阵无需进行乘法操作； - 当i < j时，m[i][j] = min{m[i][k] + m[k+1][j] + pi-1 × pk × pj}，其中i ≤ k < j。

填表计算最优值根据状态转移方程，我们可以使用动态规划的方法逐步填充表格m。

具体步骤如下：1. 初始化所有m[i][i]为0（0 ≤ i ≤ n）； 2. 对于每个子问题(i, j)，从i= 1递增到j = n-1，按照递增的长度进行计算： - 对于每个i和j，根据状态转移方程计算m[i][j]； 3. 最终，m[1][n-1]即为所求的计算矩阵Ai × Ai+1× … × An的最优顺序和乘法操作总数。

重构最优解为了得到最优顺序下的具体计算过程，我们可以使用一个辅助表格s来记录最优划分点。

摘要算法设计与分析，其实可以解释为一类优化问题，一般针对可以利用计算机解决的离散型问题的优化。

主要目的就是为了解决某一问题而提出的各种不同的解决方案。

本文通过计算机算法分析设计出解矩阵连乘的动态规划算法和设计出解批处理作业调度的回溯法算法，利用C++语言编写程序实现算法。

动态规划算法是将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

首先找出最优解的性质，并刻其结构特征，然后递归的定义最优值（写出动态规划方程）并且以自底向上的方式计算出最优值，最后根据计算最优值时得到的信息，构造一个最优解。

回溯法算法是确定了解空间的组织结构后，回溯法就是从开始节点（根结点）出发，以深度优先的方式搜索整个解空间。

这个开始节点就成为一个活结点，同时也成为当前的扩展结点。

在当前的扩展结点处，搜索向纵深方向移至一个新结点。

这个新结点就成为一个新的或节点，并成为当前扩展结点。

如果在当前的扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。

换句话说，这个节点，这个结点不再是一个活结点。

此时，应往回（回溯）移动至最近一个活结点处，并使这个活结点成为当前的扩展结点。

回溯法即以这种工作方式递归的在解空间中搜索，直到找到所要求的解或解空间中以无活结点为止。

即通过确定初始解和剪枝函数原则画出状态图进行搜索产生全部可行解。

关键词：动态规划；矩阵连乘；回溯法；批处理作业调度；剪枝原则； C++目录一、课程设计目的 (1)二、课程设计内容 (1)三、概要设计 (1)3.1 动态规划—矩阵连乘 (1)3.2 回溯法—批处理作业调度 (2)四、详细设计与实现 (3)4.1动态规划—矩阵连乘 (3)4.11 问题描述 (3)4.12分析最优解的结构 (3)4.13建立递归关系 (3)4.14计算最优值 (4)4.15代码实现 (4)4.16 运行结果 (7)4.2回溯法—批处理作业调度 (8)4.21 问题描述 (8)4.22 算法分析 (8)4.23 代码实现 (9)4.24 运行结果 (12)总结 (14)参考文献 (15)一、课程设计目的《计算机算法设计与分析》这门课程是一门实践性非常强的课程，要求我们能够将所学的算法应用到实际中，灵活解决实际问题。

矩阵连乘问题为了能够清楚地描述矩阵连乘的问题，我在此给出以下定义：1.在给定的n个矩阵{A1,A2,……,An}中Ai与Ai+1是可乘的2.A[m][n]表示一个m行n列的矩阵3.由于矩阵连乘满足结合律，故A1(A2A3)表示，先计算A2A3,得出一个新的矩阵再与A1相乘。

4.A[i:j]表示矩阵A[i]、A[i+1]、A[i+2]、……、A[j]5.min[i][j]表示矩阵A[i]到矩阵A[j]这j-i个矩阵的最小数乘次数6.P[i]表示矩阵A[i]的行数7.P[i+1]表示矩阵A[i]的列数及矩阵A[i+1]的行数问题的引出：现给出矩阵A[2][3]和A[3][2]，如果计算A[2][3] *A[3][2]，则根据矩阵运算法则要进行2*3*2=12次乘法运算。

而如果要计算A[3][2]* A[2][3]，则要进行3*2*3=18次乘法运算。

而两个矩阵相乘很容易使用穷举法来判断出数乘次数最少的计算次序。

但是，对于多个矩阵来说，如何能够尽快的获取最优（即数乘次数最少）的连乘次序呢？矩阵连乘问题的描述：给定n个矩阵{A1,A2,…,An}，如何确定一种数乘次数最小的数乘次序，这就是矩阵连乘问题。

问题的分析：假设计算A[i:j]当i=j时，A[i:j]=Ai;矩阵min[i][j]=0，即单个矩阵数乘次数为0。

当i<j时，若计算A[i:j]的最优次序，假设在A[k] 和A[k+1]之间断开(i<k<k+1<j)，,即(AiAi+1…Ak)(Ak+1…Aj)则可有递归式，min[i][j]=min[i][k]+min[k+1][j]+P[i-1]*P[i]*p[j];有必要引入数组m[i][j]以存储min[i][j]的值，是为了存储已经解决的子问题的答案，防止相同的子问题反复求解.例如：在求m[2][7],m[2][8],m[2][9],都会用到m[2][3],m[2][4],m[2][5]和m[2][6]如果每次使用m[2][3],m[2][4],m[2][5]和m[2][6]时，都重新使用递归运算求解的话，那么将会浪费大量的时间。