求教一个关于动态规划矩阵连乘算法的有关问题,请大家帮忙看下
求教一个关于动态规划矩阵连乘算法的问题,请大家帮忙看下!
求教一个关于动态规划矩阵连乘算法的问题:
void MatrixChain(int *p,int n,int **m,int **s)
{
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;}
}
}
}
A1 A2 A3 A4 A5 A6
30*35 35*15 15*5 5*10 10*20 20*25
p1p2p5这个为什么是35*15*20啊,课本上我看了半天没看懂。这个p1 p2 p5应该如何取值啊?求高手赐教!!!
------解决方案--------------------
1
求教一个关于动态规划矩阵连乘算法的问题:
void MatrixChain(int *p,int n,int **m,int **s)
{
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;}
}
}
}
A1 A2 A3 A4 A5 A6
30*35 35*15 15*5 5*10 10*20 20*25
p1p2p5这个为什么是35*15*20啊,课本上我看了半天没看懂。这个p1 p2 p5应该如何取值啊?求高手赐教!!!
------解决方案--------------------
1