#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
typedef struct matrix
{
int row;
int col;
} matrix;
typedef struct minCost
{
int cost;
int mid;
} minCost;
minCost** func(matrix* mt, ssize_t count)
{
int i, j, step, min, temp, mid;
minCost **rows;
rows = (minCost **)malloc(count*(sizeof(minCost*)));
for(i=0;i<count;i++)
rows[i] = (minCost *)malloc((count-i)*sizeof(minCost));
for(i=0;i<count;i++)
{
rows[i][0].cost=0;
rows[i][0].mid=-1;
}
for(step=1;step<count;step++)
for(j=0;j<count-step;j++)
{
min=mt[j].row*mt[j].col*mt[j+step].col
+rows[j][0].cost+rows[j+1][step-1].cost;//__page_break__
mid=j;
for(i=1;i<step;i++)
{
temp=rows[j][i].cost+rows[j+i+1][step-i-1].cost
+mt[j].row*mt[j+i].col*mt[j+step].col;
if(min>temp)
{
min=temp;
mid=j+i;
}
}
rows[j][step].cost=min;
rows[j][step].mid=mid;
}
printf("%d, %d\n", rows[0][count-1].cost, rows[0][count-1].mid);
return rows;
}
int rel(minCost **mc, ssize_t count)
{
int i;
for(i=0;i<count;i++)
free(mc[i]);
free(mc);
}
int main(int argc, char *argv[])
{
minCost **temp;
matrix ma[]={{30,35},{35,15},{15,5},{5,10},{10,20},{20,25}};
temp=func(ma, sizeof(ma)/sizeof(ma[0]));
rel(temp, sizeof(ma)/sizeof(ma[0]));
}
<This article edit by Zhao Jia Wei and from: http://www.dreamblow.cn/.>
