#include<stdio.h>
#define LENGTH 7
int Mco(int* p, int (*m)[LENGTH], int (*s)[LENGTH]);
int LookUp(int i, int j);
int p[] = {30, 35, 15, 5, 10, 20, 25};
int m[LENGTH][LENGTH];
int s[LENGTH][LENGTH];
void TraceBack(int i, int j);
int Mco(int* p, int (*m)[LENGTH], int (*s)[LENGTH])
{
int i, j;
for(i=0; i< LENGTH; i++){
for(j=i; j< LENGTH; j++){
m[i][j] = 0;
}
}
return LookUp(1, LENGTH-1);
}
int LookUp(int i,int j)
{
int u = 0, k;
if(m[i][j]) return m[i][j];
if(i == j) return 0;
u = LookUp(i+1, j) + p[i-1] * p[i] * p[j];
s[i][j] = i;
for( k = i+1; k < j; k++){
int t = LookUp(i, k) + LookUp(k+1, j) + p[i-1] * p[k] * p[j];
if(u > t){
s[i][j] = k;
u = t;
}
}
m[i][j] = u;
return u;
}
void TraceBack(int i, int j)
{
if(i == j) return ;
TraceBack(i, s[i][j]);
TraceBack(s[i][j]+1, j);
printf("%d,%d", i, s[i][j]);
printf("%d,%d", s[i][j]+1, j);
printf("/n");
}
int main()
{
int t = Mco(p, m, s);
TraceBack(1, LENGTH-1);
system("pause");
return 0;
}
########################################################非递归
#include<stdio.h>
#define LENGTH 6
int Mco(int n);
int LookUp(int i, int j);
int p[] = {30, 35, 15, 5, 10, 20, 25};
int m[LENGTH][LENGTH];
int s[LENGTH][LENGTH];
void TraceBack(int i, int j);
int Mco(int n)
{
int i, j, r, u, k, t;
for(i=0; i< n; i++){
m[i][i] = 0;
}
i = 0;
for(r = 1; r < n; r++){
for(i = 0; i < n - r; i++){
j = i + r;
m[i][j] = m[i+1][j] + p[i]*p[i+1]*p[j+1];
s[i][j] = i;
for(k = i + 1; k < j; k++){
t = m[i][k] + m[k+1][j] + p[i]*p[k+1]*p[j+1];
if(m[i][j] > t){
m[i][j] = t;
s[i][j] = k;
}
}
}
}
return m[0][n-1];
}
void TraceBack(int i, int j)
{
if(i == j) return ;
TraceBack(i, s[i][j]);
TraceBack(s[i][j]+1, j);
printf("%d,%d", i, s[i][j]);
printf("%d,%d", s[i][j]+1, j);
printf("/n");
}
int main()
{
int t = Mco(LENGTH);
printf("%d/n", t);
TraceBack(0, LENGTH-1);
system("pause");
return 0;
}