} if(i==j) return0; intu=LookupChain(i,i)+LookupChain(i+1,j)+p[i-1]*p[i]*p[j]; s[i][j]=i; for(intk=i+1;k<j;k++) { intt=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; returnu;}intMemoizedMatrixChain(intn,int**m,int**s){ for(inti=1;i<=n;i++) for(intj=i;j<=n;j++)m[i][j]=0; //把?m[i][j]的?矩?陣ó的?上?三▂角?全?部?賦3值μ為a0。￡returnLookupChain(1,n);}//動(dòng)ˉ態(tài)?規(guī)?劃?法ぁ?voidMatrixChain(){ for(inti=1;i<=n;i++) { m[i][i]=0; } for(intr=2;r<=n;r++) { for(inti=1;i<=n-r+1;i++) {intj=r+i-1;m[i][j]=m[i][i]+m[i+1][j]+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;k<j;k++) {inttemp=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];if(temp<m[i][j]) {m[i][j]=temp; s[i][j]=k; }} } }}//直±接ó遞蘗歸é法ぁ?intRecurMatrixChain(inti,intj){ if(i==j){return0;} intu=RecurMatrixChain(i,i)+RecurMatrixChain(i+1,j)+p[i-1]*p[i]*p[j];//遞蘗歸é，?p[]為a維?數(shù)簓 s[i][j]=i;//記?錄?加ó括ぁ?號(hào)?的?位?置? for(intk=i+1;k<j;k++) { intt=RecurMatrixChain(i,k)+RecurMatrixChain(k+1,j)+p[i-1]*p[k]*p[j];//遞蘗歸é if(t<u){u=t;s[i][j]=k;}//判D斷?哪?個(gè)?值μ更ü小?，?選?取?哪?個(gè)? } returnu;}voidTraceback(inti,intj){if(i==j)//如?果?只?有瓺一?個(gè)?矩?陣ó，?則ò直±接ó輸?出?{cout<<"A"<<i;}elseif(i+1==j)//加ó括ぁ?號(hào)?輸?出?{cout<<"(A"<<i<<"A"<<j<<")";}else{cout<<"(";Traceback(i,s[i][j]);Traceback(s[i][j]+1,j);cout<<")";}}MatrixMultiply.cpp#include<iostream>#include"matrix.h"usingnamespacestd;//intn;//定¨義?一?個(gè)?全?局?變?量?intmain(){L: intchoice; cout<<"請(qǐng)輸入相乘的矩陣的個(gè)數(shù)n="; cin>>n; cout<<"請(qǐng)輸入第1個(gè)矩陣行數(shù)和第1個(gè)矩陣到第"<<n<<"個(gè)矩陣的列數(shù)："; for(inti=0;i<=n;i++) { cin>>p[i]; } cout<<endl; cout<<"請(qǐng)選擇矩陣連乘的算法:"<<endl; cout<<"1.備忘錄算法"<<endl; cout<<"2.直接遞歸算法"<<endl; cout<<"3.動(dòng)態(tài)規(guī)劃算法"<<endl; cout<<"4.重新輸入矩陣"<<endl; cout<<"5.退出程序"<<endl;cout<<endl; cout<<"請(qǐng)輸入選擇的編號(hào)："; cin>>choice; cout<<endl; while(choice!=5){ switch(choice){ case1:LookupChain(1,n); cout<<"動(dòng)態(tài)規(guī)劃算法："<<endl; cout<<"矩陣連乘的最優(yōu)值為："<<m[1][n]<<endl; cout<<"矩陣連乘的最優(yōu)解為："; Traceback(1,n); cout<<endl; break; case2: RecurMatrixChain(0,n); cout<<"動(dòng)態(tài)規(guī)劃算法："<<endl; cout<<"矩陣連乘的最優(yōu)值為："<<m[1][n]<<endl; cout<<"矩陣連乘的最優(yōu)解為："; Traceback(1,n); cout<<endl; break; case3: MatrixChain(); cout<<"動(dòng)態(tài)規(guī)劃算法："<<endl; cout<<"矩陣連乘的最優(yōu)值為："<<m[1][n]<<endl; cout<<"矩陣連乘的最優(yōu)解為："; Traceback(1,n); cout<<endl; break; case4: gotoL; break; case5: choice=4; break; default: break;} cout<<endl; cout<<"請(qǐng)選擇矩陣連乘的算法:"<<endl; cout<<"1.備忘錄算法"<<endl; cout<<"2.直接遞歸算法"<<endl