Java代码：
public class MatrixChain { public static void main(String[] args) { int p[] = {30, 35, 15, 5, 10, 20, 25, 30, 40}; // 30×35 35×15 15×5 5×10 10×20 20×25 25×30 30×40 int n = p.length - 1; // 矩阵个数 int[][] arr = new int[n + 1][n + 1]; int[][] d = new int[n + 1][n + 1]; StringBuffer sb = new StringBuffer(); for (int i = 65; i < 65 + n; i++) { sb.append((char)i); } String s = ""; //第一个 System.out.println("方法1：由下至上："); func1(n, arr, p, d); s = outputString(1, n, d, sb.toString()); System.out.println("最优解为：" + s.substring(1, s.length() - 1)); System.out.println("-------------------------------------------"); System.out.println("方法2：由上至下（备忘录）："); //第二个 System.out.println(func2(1, n, p, arr, d)); s = outputString(1, n, d, "ABCDEFGH"); System.out.println("最优解为：" + s.substring(1, s.length() - 1)); } // 这又是一个算法啊 public static String outputString(int i, int j, int[][] d, String s) { // ABC DEF if (i == j) { return String.valueOf(s.charAt(i - 1)); } int k = d[i][j]; // i 1 j 6 k 3 return "(" + outputString(i, k, d, s) + outputString(k + 1, j, d, s) + ")"; } public static int func2(int i, int j, int[] p, int[][] arr, int[][] d) { for (int x = 0; x < p.length; x++) { for (int y = 0; y < arr[x].length; y++) { arr[x][y] = -1; } } if (arr[i][j] != -1) return arr[i][j]; if (i == j) { arr[i][j] = 0; return 0; } int ans, minV = 9999999; //System.out.println("(" + i + "," + j + ")");//查看调用次序 for (int k = i; k < j; k++) { ans = func2(k + 1, j, p, arr, d) + func2(i, k, p, arr, d) + p[i - 1] * p[k] * p[j]; if (ans < minV) { minV = ans; d[i][j] = k; } } arr[i][j] = minV; return minV; } public static void func1(int n, int[][] arr, int[] p, int[][] d) { for (int i = 1; i <= n; i++) { arr[i][i] = 0; } //i表示要计算矩阵的长度，先计算短矩阵 for (int len = 2; len <= n; len++) { //矩阵开始长度j表示 for (int start = 1; start <= n - len + 1; start++) { int end = start + len - 1; //矩阵结束位置 arr[start][end] = 9999999; //一个充分大的数 for (int k = start; k < end; k++) { int sum = arr[start][k] + arr[k + 1][end] + p[start - 1] * p[k] * p[end]; if (sum < arr[start][end]) { arr[start][end] = sum; d[start][end] = k; } } } } System.out.println(arr[1][p.length - 1]); } }运行结果：
