fork(1) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
11875
https://ideone.com/BcxLA9
language:
Java (12.0.1)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!