m[1][4]
├── k=1: m[1][1] + m[2][4]
│         └── m[2][4] → m[2][2]+m[3][4] , m[2][3]+m[4][4]
│                       └── m[2][3] → ...
├── k=2: m[1][2] + m[3][4]
│         ├── m[1][2] → ...
│         └── m[3][4] → ...
└── k=3: m[1][3] + m[4][4]
          └── m[1][3] → m[1][1]+m[2][3] , m[1][2]+m[3][3]
                        └── m[2][3] → ...   ← 与上面的 m[2][3] 重复

for r = 2 to n:                    // 区间长度
    for i = 1 to n - r + 1:        // 区间起点
        j = i + r - 1              // 区间终点
        m[i][j] = min{ m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j] }  (i <= k < j)

/** 由 s 表自顶向下回溯，输出最优加括号方案 */
private String buildOptimalParens(int i, int j) {
    if (i == j) {                       // 单个矩阵，递归出口
        return "A" + i;
    }
    int k = s[i][j];                    // 最优划分点
    return "(" + buildOptimalParens(i, k)
               + buildOptimalParens(k + 1, j) + ")";
}

s[1][6] = 3  →  ( A1..A3 )( A4..A6 )
s[1][3] = 1  →  ( A1 )( A2..A3 )
s[2][3] = 2  →  ( A2 )( A3 )
s[4][6] = 5  →  ( A4..A5 )( A6 )
s[4][5] = 4  →  ( A4 )( A5 )

合并结果：((A1(A2A3))((A4A5)A6))

import java.util.Arrays;

/**
 * 矩阵连乘问题：求计算 A1A2...An 所需的最少标量乘法次数，并给出最优加括号方案。
 */
public class MatrixChain {

    /** 维度数组 p：第 i 个矩阵 Ai 的规模为 p[i-1] × p[i]，长度为 n+1 */
    private final int[] p;
    /** m[i][j]：计算 Ai..Aj 所需的最少乘法次数，仅用 1..n 下标 */
    private final long[][] m;
    /** s[i][j]：使 m[i][j] 取到最小值的划分位置 k，用于回溯构造最优解 */
    private final int[][] s;
    private final int n;

    public MatrixChain(int[] p) {
        this.p = p;
        this.n = p.length - 1;
        this.m = new long[n + 1][n + 1];
        this.s = new int[n + 1][n + 1];
    }

    /** 自底向上动态规划：按链长 r 递增填表，时间复杂度 O(n^3)，空间复杂度 O(n^2) */
    public long solve() {
        // 链长为 1 时无需相乘，代价为 0（m 数组默认即为 0）
        for (int r = 2; r <= n; r++) {              // r 为子链长度
            for (int i = 1; i <= n - r + 1; i++) {  // i 为子链起点
                int j = i + r - 1;                  // j 为子链终点
                m[i][j] = Long.MAX_VALUE;
                for (int k = i; k < j; k++) {       // 枚举最后一次相乘的划分点
                    long cost = m[i][k] + m[k + 1][j]
                            + (long) p[i - 1] * p[k] * p[j];
                    if (cost < m[i][j]) {
                        m[i][j] = cost;
                        s[i][j] = k;
                    }
                }
            }
        }
        return m[1][n];
    }

    /** 由 s 表自顶向下回溯，输出最优加括号方案，如 ((A1(A2A3))((A4A5)A6)) */
    public String buildOptimalParens() {
        return buildOptimalParens(1, n);
    }

    private String buildOptimalParens(int i, int j) {
        if (i == j) {
            return "A" + i;
        }
        int k = s[i][j];
        return "(" + buildOptimalParens(i, k) + buildOptimalParens(k + 1, j) + ")";
    }

    /** 打印 m 表和 s 表的上三角部分，便于人工核对填表过程 */
    public void printTables() {
        System.out.println("m 表（最少乘法次数）：");
        for (int i = 1; i <= n; i++) {
            StringBuilder line = new StringBuilder();
            for (int j = 1; j <= n; j++) {
                line.append(j < i ? String.format("%10s", "-") : String.format("%10d", m[i][j]));
            }
            System.out.println(line);
        }
        System.out.println("s 表（最优划分点 k）：");
        for (int i = 1; i <= n; i++) {
            StringBuilder line = new StringBuilder();
            for (int j = 1; j <= n; j++) {
                line.append(j < i ? String.format("%5s", "-") : String.format("%5d", s[i][j]));
            }
            System.out.println(line);
        }
    }

    /** 备忘录法（自顶向下递归 + 记忆化），与自底向上 DP 结果一致 */
    public static long memoized(int[] p) {
        int n = p.length - 1;
        long[][] memo = new long[n + 1][n + 1];
        for (long[] row : memo) {
            Arrays.fill(row, -1);
        }
        return lookup(p, memo, 1, n);
    }

    private static long lookup(int[] p, long[][] memo, int i, int j) {
        if (i == j) {
            return 0;
        }
        if (memo[i][j] >= 0) {           // 查表命中，直接返回，避免重复计算
            return memo[i][j];
        }
        long best = Long.MAX_VALUE;
        for (int k = i; k < j; k++) {
            best = Math.min(best, lookup(p, memo, i, k) + lookup(p, memo, k + 1, j)
                    + (long) p[i - 1] * p[k] * p[j]);
        }
        memo[i][j] = best;               // 记录子问题解
        return best;
    }

    public static void main(String[] args) {
        // 六个矩阵：A1=30×35, A2=35×15, A3=15×5, A4=5×10, A5=10×20, A6=20×25
        int[] p = {30, 35, 15, 5, 10, 20, 25};

        MatrixChain chain = new MatrixChain(p);
        long min = chain.solve();
        System.out.println("最少乘法次数：" + min);
        System.out.println("最优加括号方案：" + chain.buildOptimalParens());
        System.out.println("备忘录法校验：" + memoized(p));
        System.out.println();
        chain.printTables();

        // 对比：顺序相乘 ((((A1A2)A3)A4)A5)A6) 的代价
        long leftToRight = 0;
        for (int i = 1; i < p.length - 1; i++) {
            leftToRight += (long) p[0] * p[i] * p[i + 1];
        }
        System.out.println();
        System.out.println("从左到右顺序相乘的代价：" + leftToRight);
    }
}

最少乘法次数：15125
最优加括号方案：((A1(A2A3))((A4A5)A6))
备忘录法校验：15125

m 表（最少乘法次数）：
         0     15750      7875      9375     11875     15125
         -         0      2625      4375      7125     10500
         -         -         0       750      2500      5375
         -         -         -         0      1000      3500
         -         -         -         -         0      5000
         -         -         -         -         -         0
s 表（最优划分点 k）：
    0    1    1    3    3    3
    -    0    2    3    3    3
    -    -    0    3    3    3
    -    -    -    0    4    5
    -    -    -    -    0    5
    -    -    -    -    -    0

从左到右顺序相乘的代价：40500