fork download
  1. import java.util.*;
  2. import java.lang.*;
  3.  
  4. class Main
  5. {
  6. public static int MemoizedMatrixChain(final int[] p) {
  7. int n = p.length - 1;
  8. int[][] m = new int[n][n];
  9. for (int i = 0; i < n; i++) {
  10. for (int j = i; j < n; j++) {
  11. m[i][j] = Integer.MAX_VALUE;
  12. }
  13. }
  14. return lookUpChain(m, p, 1, n - 1);
  15. }// MemoizedMatrixChain
  16.  
  17. public static int lookUpChain(final int[][] m, final int[] p, final int i, final int j) {
  18. if (m[i][j] > Integer.MAX_VALUE) {
  19. return m[i][j];
  20. }
  21. if (i == j) {
  22. m[i][j] = 0;
  23. } else {
  24. for (int k = i; k <= j - 1; k++) {
  25. int q = lookUpChain(m, p, i, k) + lookUpChain(m, p, k + 1, j) + p[i - 1] * p[k] * p[j];
  26. if (q < m[i][j]) {
  27. m[i][j] = q;
  28. }
  29. }
  30. }
  31. return m[i][j];
  32. }
  33.  
  34. public static void main(final String[] args) {
  35. // TODO Auto-generated method stub
  36. int[] arr = { 30, 35, 15, 5, 10, 20, 25 };
  37. int result = MemoizedMatrixChain(arr);
  38. System.out.println(result);
  39.  
  40. }// main
  41. }
Success #stdin #stdout 0.06s 380160KB
stdin
Standard input is empty
stdout
11875