Question: dynamic programming algorithm class MatrixChainMultiplication { int MatrixChainOrder(int[] d) { int n = d.length - 1; int[][] m = new int[n][n]; int i, j, k,
dynamic programming algorithm
class MatrixChainMultiplication {
int MatrixChainOrder(int[] d) {
int n = d.length - 1;
int[][] m = new int[n][n];
int i, j, k, b, q;
for (i = 0; i < n; i++)
m[i][i] = 0;
for (b = 1; b < n; b++) {
for (i = 0; i < n - b; i++) {
j = i + b;
int tmp = m[i][i] + m[i + 1][j] + d[i] * d[i + 1] * d[j + 1];
for (k = i + 1; k < j; k++) {
q = m[i][j] + m[k + 1][j] + d[i] * d[k + 1] * d[j + 1];
if (q < tmp)
tmp = q;
}
m[i][j] = tmp;
}
}
return m[0][n - 1];
}
}
How can I find Running Time of this algorithm
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
