Skip to content

Instantly share code, notes, and snippets.

@RitamChakraborty
Last active July 29, 2019 19:44
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save RitamChakraborty/da1b8ab58ee0109116dfc2ac7e9c1a27 to your computer and use it in GitHub Desktop.
Save RitamChakraborty/da1b8ab58ee0109116dfc2ac7e9c1a27 to your computer and use it in GitHub Desktop.
Matrix Chain Multiplication problem in Java
import java.util.Arrays;
import java.util.stream.IntStream;
public class MatrixChainMultiplication {
public static void main(String[] args) {
int n = 4;
int[] d = {5, 4, 6, 2, 7};
int[][] m = new int[n][n];
int[][] c = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < (n - i); j++) {
if (j != (j + i)) {
int min = Integer.MAX_VALUE;
int temp;
int a = 0;
for (int k = j; k < (j + i); k++) {
temp = m[j][k] + m[k + 1][j + i] + d[j] * d[k + 1] * d[j + i + 1];
if (temp < min) {
min = temp;
a = k + 1;
}
}
m[j][j + i] = min;
c[j][j + i] = a;
}
}
}
IntStream.range(0, n).forEach(i -> System.out.println(Arrays.toString(m[i])));
System.out.println();
IntStream.range(0, n).forEach(i -> System.out.println(Arrays.toString(c[i])));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment