矩阵连乘java

矩阵连乘问题可以使用动态规划来解决。具体来说，假设有 n 个矩阵需要相乘，它们的维度分别为 d0×d1，d1×d2，...，dn-1×dn。定义 m[i][j] 表示从第 i 个矩阵到第 j 个矩阵相乘的最小代价，s[i][j] 表示从第 i 个矩阵到第 j 个矩阵中最后一次相乘的位置，则有以下递推式：

m[i][j] = 0, (i = j)
m[i][j] = min{m[i][k] + m[k+1][j] + di-1×dk×dj}, (i <= k < j)
s[i][j] = k, (i <= k < j)

其中，i <= j，d[-1] = d[n] = 0。

根据递推式，可以使用二维数组 m 和 s 来保存中间结果，从而避免重复计算。最终，可以通过 s 数组来构造出最终的乘法顺序。

下面是 Java 代码实现：

public static void matrixChainOrder(int[] p) {
    int n = p.length - 1;
    int[][] m = new int[n][n];
    int[][] s = new int[n][n];
    for (int i = 0; i < n; i++) {
        m[i][i] = 0;
    }
    for (int l = 2; l <= n; l++) {
        for (int i = 0; i < n - l + 1; i++) {
            int j = i + l - 1;
            m[i][j] = Integer.MAX_VALUE;
            for (int k = i; k < j; k++) {
                int q = m[i][k] + m[k+1][j] + p[i]*p[k+1]*p[j+1];
                if (q < m[i][j]) {
                    m[i][j] = q;
                    s[i][j] = k;
                }
            }
        }
    }
    System.out.println("Minimum number of multiplications: " + m[0][n-1]);
    printOptimalParenthesis(s, 0, n-1);
}

public static void printOptimalParenthesis(int[][] s, int i, int j) {
    if (i == j) {
        System.out.print("A" + (i+1));
    } else {
        System.out.print("(");
        printOptimalParenthesis(s, i, s[i][j]);
        printOptimalParenthesis(s, s[i][j]+1, j);
        System.out.print(")");
    }
}

其中，数组 p 表示矩阵的维度，n 表示矩阵的个数。函数 matrixChainOrder 用来计算最小代价并输出乘法顺序，函数 printOptimalParenthesis 用来输出乘法顺序。