你说在那儿结束递归,我用return语句可以吧
我把参数改为从1开始可以吧
可是我改了后还不行
我改后的程序
#include<iostream.h>
void MatrixChain(int p[],int n,int m[6][6],int s[6][6]);
int Traceback(int i,int j,int s[6][6]);
int main()
{
int p[]={30,35,15,5,10,20,25};
int n=6;
int m[6][6];
int s[6][6];
MatrixChain(p,n,m,s);
int i=1,j=6;
Traceback(i,j,s);
return 0;
}
void MatrixChain(int p[],int n,int m[6][6],int s[6][6])
{
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]=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;
}
}
}
}
int Traceback(int i,int j,int s[6][6])
{
if(i==j)return 0;//cout<<"no-op"<<endl;
Traceback(i,s[i][j],s);
Traceback(s[i][i]+1,j,s);
cout<<"Multiply A"<<i<<","<<s[i][j];
cout<<"and A"<<(s[i][j]+1)<<","<<j<<endl;
}

[此贴子已经被作者于2007-11-20 9:11:57编辑过]

刚学矩阵,受教了

[CODE]/*
题目：矩阵链乘法
问题描述：
给定N个矩阵构成一个链<A1,A2,A3，…,An>，其中i=1，2，…n，矩阵Ai的维数为
Pi-1 * Pi，对乘积A1A2A3…An以一种最小化标量乘法次数的方式进行加全部括号。

from：Introduction to Algorithms Page 331
*/
#include <iostream>
using namespace std;
const int MAX = 101;
#define N 6
int dp[MAX][MAX]; //for storing best sub-slutions
//2d array use the part(i<=j) dp[i][j] to store minnimum time for multiply of Ai..Aj
//the rest part(i>j) dp[j][i] to store best divider of Ai..Aj
int p[N+1] = {30,35,15,5,10,20,25}; //matrix list
/* versin1
//recursive function to print the solution
void print(int (*)[MAX],int,int);
int main(){
//dynamic programming for the problem
//down-top approach

//use the length increasing to make the dp table
int i,j,l,k,t;
for (i = 1;i <= N;++i)
dp[i][i] = 0; //no cost if only 1 matrix (length is 1)

for (l = 2;l <= N;++l)
for (i = 1;i <= N-l+1;++i){
j = i+l-1;
for (k = i;k <= j-1;++k){
t = dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j];
if (k == i || dp[i][j] > t){
dp[i][j] = t;
dp[j][i] = k;
}
}
}

//the the dp over and the problem is sloved

//print the answers

cout << "minimum multiply of the matrix list is : " << dp[1][N] << endl;
print(dp,N,1);

cout << endl;

//for testing
// for (int m = 1;m <= N;++m){
// for (int n = 1;n <= N;++n)
// cout << dp[m][n] << " ";
// cout << endl;
// }

system("pause");
}
*/
void print(int (*dp)[MAX],int j,int i){
if (j == i)
cout << "A" << i;
else{
cout << "(";
print(dp,dp[j][i],i);
print(dp,j,dp[j][i]+1);
cout << ")";
}
}
//use memo technology to solve problem of top-down approach
int memo_lookup(int (*dp)[MAX],int *p,int i,int j){
if (dp[i][j] >= 0)
return dp[i][j];
if (i == j)
dp[i][j] = 0;
else
for (int k = i,t;k < j;++k){
t = memo_lookup(dp,p,i,k)+memo_lookup(dp,p,k+1,j)+p[i-1]*p[k]*p[j];
if (dp[i][j] < 0 || t < dp[i][j])
dp[i][j] = t;
}
return dp[i][j];
}
int solution(int (*dp)[MAX],int *p,int i,int j){
for (int m1 = 1;m1 <= j;++m1)
for (int m2 = m1;m2 <= j;++m2)
dp[m1][m2] = -1;
return memo_lookup(dp,p,i,j);
}

int main(){

cout << "minimum multiply of the matrix list is : "
<< solution(dp,p,1,N) << endl;
system("pause");
}


/*
使用动态规划的两个要素：1）最优子结构；2）子问题独立重叠

*/ [/CODE]

学习笔记，注意注释代码，看懂了应该可以自行选择运行。