动态规划算法的基本思想：

将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解，与分治法不同的是，适用于动态规划求解的问题，经分解得到的子问题往往不是相互独立的；

大致思路：

只要被计算过的，就将其结果填入表中，以后用到的时候去查表。

#include<iostream>

  using namespace std;

  const int MAX = 100;

 //p用来记录矩阵的行列，main函数中有说明

 //m[i][j]用来记录第i个矩阵至第j个矩阵的最优解

 //s[][]用来记录从哪里断开的才可得到该最优解

  //n矩阵个数

 int p[MAX+1],m[MAX][MAX],s[MAX][MAX];

 int n;//矩阵个数

 

 

 void MatrixChain(int *p,int n,int **m,int **s){

     for(int i=1;i<=n;i++)

m[i][i]=0;

for(int r=2;r<=n;r++)//对角线循环

for(int i=1;i<=n-r+1;i++){//行循环

    int j=i+r-1;//列的控制

 //找m[i][j]的最小值，先初始化一下，令k=i

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]=k;

}

}

}

 }

 //根据s[][]记录的各个子段的最优解，将其输出

 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;

 }

 

 

int main(void ){     int  n=6;//矩阵的个数      int *p=new int[n+1];      //p[0]:第一个矩阵的行数        //p[1]:第一个矩阵的列数，第二个矩阵的行数        //p[2]:第二个矩阵的列数，第三个矩阵的行数      p[0]=30;      p[1]=35;      p[2]=15;      p[3]=5;      p[4]=10;      p[5]=20;      p[6]=25;        int **m,**s;      m=new int*[n+1];      for( int i=0;i