用java写一个动态规划算法之矩阵链乘法

在Java中，我们可以使用动态规划(Dynamic Programming)来解决矩阵链乘法的问题，这是一个经典的计算机科学问题，涉及到递归和优化。矩阵链乘法的目标是最优地计算一系列矩阵相乘的操作序列，以便最小化所需的总乘法次数。

以下是一个简单的Java代码实现矩阵链乘法的动态规划算法：

class Solution {
    public int matrixChainOrder(int[][] p) {
        if (p.length == 0 || p.length == 1) return 0; // 如果只有一个矩阵或没有矩阵，直接返回0

        int n = p.length;
        int[][] dp = new int[n - 1][n]; // dp[i][j] 表示拆分i到j之间的矩阵需要的最优操作数

        for (int l = 2; l < n; l++) { // 遍历所有可能的子矩阵大小
            for (int i = 0; i + l - 1;
                dp[i][j] = Integer.MAX_VALUE; // 初始设置为最大值
                for (int k = i; k < j; k++) { // 遍历中间节点k
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + p[i][k] * p[k + 1][j]); // 更新最优路径
                }
            }
        }

        return dp[0][n - 1]; // 返回最终的最优解，即整个矩阵链乘法的最小乘法次数
    }
}