T******7
发帖数: 1419 | 1 #include
#include
// Matrix Ai has dimension p[i-1] x p[i] for i = 1..n
int MatrixChainOrder(int p[], int n)
{
/* For simplicity of the program, one extra row and one extra column are
allocated in m[][]. 0th row and 0th column of m[][] are not used */
int m[n][n];
int i, j, k, L, q;
/* m[i,j] = Minimum number of scalar multiplications needed to compute
the matrix A[i]A[i+1]...A[j] = A[i..j] where dimention of A[i] is
p[i-1] x p[i] */
// cost is zero when multiplying one matrix.
for (i = 1; i < n; i++)
m[i][i] = 0;
// L is chain length.
for (L=2; L
{
for (i=1; i<=n-L+1; i++)
{
j = i+L-1;
m[i][j] = INT_MAX;
for (k=i; k<=j-1; k++)
{
// q = cost/scalar multiplications
q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
if (q < m[i][j])
m[i][j] = q;
}
}
}
return m[1][n-1];
}
int main()
{
int arr[] = {1, 2, 3, 4};
int size = sizeof(arr)/sizeof(arr[0]);
printf("Minimum number of multiplications is %d ",
MatrixChainOrder(arr, size));
getchar();
return 0;
}
Time Complexity: O(n^3)
Auxiliary Space: O(n^2) | y****9
发帖数: 252 | | x******r
发帖数: 3489 | 3 算法和coding本来就很美。
和程序谈恋爱，在程序中醉生梦死，了此余生，省去很多烦恼。
功夫还不够，继续谈。 | V******J
发帖数: 9 | 4 Minor issue with the code: number of matrix shall be n, not n-1. |
|
