class MatrixChainOrder {
public static void main(String[] args) {
int[] sizes = {
10,
100,
5,
50
};
long m = memoizedMatrixChain(sizes);
System.out.println("m: " + m);
}
public static long memoizedMatrixChain(int[] p) {
int n = p.length - 1;
long[][] m = new long[n][n];
for (int i = 0; i < n; i ++) {
for (int j = i; j < n; j ++) {
m[i][j] = Long.MAX_VALUE / 2;
}
}
return lookupChain(m, p, 0, n - 1);
}
public static long lookupChain(long[][] m, int[] p, int i, int j) {
if (m[i][j] >= 0)
return m[i][j];
if (i == j)
m[i][j] = 0;
else
for (int k = i; k < j - 1; k ++) {
long q = lookupChain(m, p, i, k)
+ lookupChain(m, p, k+1, j)
+ p[i] * p[k] * p[j];
if (q < m[i][j] || m[i][j] < 0)
m[i][j] = q;
}
return m[i][j];
}
}
