算法导论第十五章--动态规划的变形（做备忘录的递归算法）

动态规划中的 循环结构可以通过递归的方式实现，但是单纯的递归方法每次都会将已计算过的子问题重新计算，时间复杂度较高，因此可以通过在递归中做备忘录的方法建设时间复杂度。具体见代码：

#include<iostream>using namespace std;//动态规划的一种变种，通过在递归的算法中添加备忘，来维护记录子问题的表格。这种方法是一种自顶向下的//方法，该方法优于单纯的递归调用，因为单纯的递归调用每次都要重新计算已经计算过的子问题，但是这种//添加备忘的递归算法大部分情况下都没有非递归的算法好，因为非递归的动态规划不需花费额外的递归代价void MemorizedMatrixChain(int *p,int (*m)[10],int (*t)[10],int length){int LookUpChain(int *p,int (*m)[10],int (*t)[10],int i,int j);int i,j,k,n;n=length-1;for(i=1;i<=n;i++){for(j=i;j<=n;j++){m[i][j]=0x7ffffff;}}m[1][n]=LookUpChain(p,m,t,1,n);}int LookUpChain(int *p,int (*m)[10],int (*t)[10],int i,int j){int q;//如果m[i][j]不是无穷大则说明m[i][j]已经被下一层的LookUpChain计算出来if(m[i][j]<0x7ffffff){return m[i][j];}//m[i][i]为0if(i==j){m[i][j]=0;}else{int k;for(k=i;k<=j-1;k++){q=LookUpChain(p,m,t,i,k)+LookUpChain(p,m,t,k+1,j)+p[i-1]*p[k]*p[j];if(q<m[i][j]){m[i][j]=q;t[i][j]=k;}}}return m[i][j];}void PrintAnswer(int(*t)[10],int i,int j){if(i==j){cout<<"A"<<i;}else{cout<<"(";PrintAnswer(t,i,t[i][j]);PrintAnswer(t,t[i][j]+1,j);cout<<")";}}int main(){int p[7]={30,35,15,5,10,20,25};int m[10][10],t[10][10];//MatrixChainOrder(p,m,t,7);MemorizedMatrixChain(p,m,t,7);PrintAnswer(t,1,6);return 0;}