經(jīng)典DP，矩陣鏈乘，不過此題不要求算最小的相乘次數(shù)，而要把最優(yōu)的解輸出，那一個數(shù)組記錄從i到j(luò)的最優(yōu)分割，然后遞歸輸出就行了。
而關(guān)于具體的轉(zhuǎn)移方程資料到處都有。就不做說明了，具體參見代碼。
代碼是O(n^3)此方的解法，據(jù)說斯坦福大學(xué)的一片論文有O(nlogn)的，改天研究下。。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 15
struct Array
{
int row, col;
}array[N];
int a[N][N], p[N][N];
void show(int left, int right)
{
if(left < right)
{
printf("(");
show(left, p[left][right]);
printf(" x ");
show(p[left][right] + 1, right);
printf(")");
}
else if(left == right)
{
printf("A%d", left);
}
}
int main()
{
int n, cas = 0;
while(scanf("%d", &n), n)
{
for(int i = 1; i <= n; i++)
scanf("%d %d", &array[i].row, &array[i].col);
memset(a, 127, sizeof(a));
memset(p, 0, sizeof(p));
for(int i = 1; i <= n; i++) a[i][i] = 0;
for(int i = 2; i <= n; i++)
{
a[i - 1][i] = array[i - 1].row * array[i].row * array[i].col;
p[i - 1][i] = i - 1;
}
for(int i = 3; i <= n; i++)
for(int j = i - 2; j; j--)
for(int k = j; k < i; k++)
{
int t = a[j][k] + a[k + 1][i] + array[j].row * array[k].col * array[i].col;
if(a[j][i] > t)
{
a[j][i] = t;
p[j][i] = k;
}
}
printf("Case %d: ", ++cas);
show(1, n);
printf("\n");
}
return 0;
}