矩阵连乘java备忘录算法

矩阵连乘问题是一个经典的动态规划问题，可以使用备忘录算法来解决。具体步骤如下：

1. 定义一个二维数组 memo，其中 memo[i][j] 表示从第 i 个矩阵到第 j 个矩阵连乘所需的最小代价。
2. 初始化 memo 数组的对角线元素为 0，即 memo[i][i] = 0。
3. 使用一个循环枚举矩阵链的长度 len，从 2 开始到 n（n 为矩阵个数）。
4. 在长度为 len 的矩阵链中，枚举起点 i，计算出终点 j = i + len - 1。
5. 对于每个起点和终点，枚举分割点 k，计算出 memo[i][j] 的值。具体计算公式为：memo[i][j] = min(memo[i][k] + memo[k+1][j] + p[i-1]*p[k]*p[j])，其中 p 数组表示矩阵的维度。
6. 最终 memo[n] 即为所求的最小代价。

Java 代码实现如下：

public static int matrixChainOrder(int[] p) {
    int n = p.length - 1;
    int[][] memo = new int[n+1][n+1];
    for (int i = 1; i <= n; i++) {
        memo[i][i] = 0;
    }
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i <= n-len+1; i++) {
            int j = i + len - 1;
            memo[i][j] = Integer.MAX_VALUE;
            for (int k = i; k < j; k++) {
                int cost = memo[i][k] + memo[k+1][j] + p[i-1]*p[k]*p[j];
                if (cost < memo[i][j]) {
                    memo[i][j] = cost;
                }
            }
        }
    }
    return memo[1][n];
}