所以P[0]和P[1]表示A₁，P[1]和[2]表示A₂以此类推即可。

1. 定义状态

​ 设dp[i][j]表示A_i到A_j所需要最小计算量，i和j从1开始计数，那么我们最终要求出的是dp[1][P.length -1]即为矩阵A₁到A_n的最小计算量，其中n = P.length -1;

​ 我么可以对dp[i][j]进行拆分，如果i和j满足j - i >= 1时，则i和j中间必有一点k，即k表示矩阵A_k。可以从A_k进行拆分两个序列(A_i到A_k)和(A_k+1到A_j)，两个序列乘法最少的计算量分别为dp[i][k]和dp[k+1][j]。两个子序列矩阵合并后计算量为P[i-1] x P[K] x P[j]。所以dp[i][j] = dp[i][k] + dp[k+1][j] + P[i-1] x P[K] x P[j]，当然位置k可能有多个，我们取最小花费那个。

2. 定义状态转移方程

当j - i <= 0时，有

​ $$dp[i][j]=0$$

否则

​ $$dp[i][j]=max(dp[i][k]+dp[k][j]+P[i-1]\times P[k]\times P[j]),i\le k<j$$

3. 初始化

​ 当j - i <= 0时，有$$dp[i][j]=0$$

4. 计算方式

​ 自底向上，自左向右计算。这里解释下是指dp二维表自底向上是指i从大往小计算，自左向右计算是指j从小到大计算。

三、代码实现

/**
 * 最小矩阵乘法运算数量
 *
 * @author hh
 * @date 2021-5-18 23:32
 */
public class MinMatrixChain {

    public int minCalcCount(int[] matrix, int[][] trace) {
        if (matrix.length < 3) {
            throw new IllegalArgumentException("非法参数");
        }
        int[][] dp = new int[matrix.length][matrix.length];
        for (int i = matrix.length - 1; i >= 1; i--) {
            for (int j = 1; j <= matrix.length-1; j++) {
                if (j - i == 0) {
                    dp[i][j] = 0;
                    continue;
                }
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = i; k < j; k++) {
                    int temp = dp[i][k] + dp[k+1][j] + matrix[i - 1] * matrix[k] * matrix[j];
                    if (temp < dp[i][j]) {
                        dp[i][j] = temp;
                        trace[i][j] = k;
                    }
                }
            }
        }
        return dp[1][matrix.length-1];
    }

    public void print(int[] matrix, int[][] trace, int startIndex, int endIndex) {
        if (endIndex - startIndex <= 0) {
            System.out.print("A" + startIndex + " ");
        } else {
            System.out.print("(");
            print(matrix, trace, startIndex, trace[startIndex][endIndex]);
            print(matrix, trace, trace[startIndex][endIndex] + 1, endIndex);
            System.out.print(")");
        }
    }

    public static void main(String[] args) {
        int[] matrix = new int[]{3, 5, 10, 8, 2, 4};
        int[][] trace = new int[matrix.length][matrix.length];
        MinMatrixChain minMatrixChain = new MinMatrixChain();
        System.out.println(minMatrixChain.minCalcCount(matrix, trace));
        minMatrixChain.print(matrix, trace, 1, matrix.length-1);
    }
}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">