每日算法 — 使用java实现区间DP：矩阵链乘与最优二叉搜索树动态规划

引言

区间动态规划（Interval Dynamic Programming，Interval DP）是动态规划家族中解决区间划分与合并问题的重要分支。与线性DP从左到右递推不同，区间DP的状态定义在区间 [i, j] 上，通过枚举分割点将大区间分解为小区间来求解。矩阵链乘（Matrix Chain Multiplication）和最优二叉搜索树（Optimal Binary Search Tree）是区间DP最经典的两道例题，它们分别代表了”合并型”和”划分型”区间DP的典型模式。本文将用Java完整实现这两种算法的动态规划解法，帮助读者建立对区间DP状态设计、递推方程与填表顺序的系统性理解。

算法原理

区间DP通用框架

区间DP的状态通常定义为：dp[i][j] 表示处理区间 [i, j] 的最优解。核心递推方程的一般形式为：

dp[i][j] = min/max { dp[i][k] ⊙ dp[k+1][j] + cost(i, j, k) }  (i ≤ k < j)

其中 ⊙ 表示某种组合运算（如加法、乘法），cost 是合并两个子区间的代价。

填表顺序：由于计算 dp[i][j] 需要所有长度小于 (j-i+1) 的区间已经计算完毕，因此按区间长度从小到大进行填表。

矩阵链乘问题

给定 n 个矩阵的链 <A₁, A₂, ..., Aₙ>，矩阵 Aᵢ 的维度为 p_{i-1} × pᵢ。目标是确定乘法顺序，使得标量乘法总次数最少。

• 状态：dp[i][j] 表示计算 Aᵢ...Aⱼ 所需的最少乘法次数。
• 递推：dp[i][j] = min{ dp[i][k] + dp[k+1][j] + p_{i-1}·p_k·p_j } (i ≤ k < j)
• 初始化：dp[i][i] = 0（单个矩阵无需乘法）

最优二叉搜索树问题

给定 n 个有序键及其搜索频率，构造一棵期望搜索代价最小的二叉搜索树。

• 状态：dp[i][j] 表示键 i 到 j 构成的最优BST的期望搜索代价。
• 递推：dp[i][j] = min{ dp[i][k-1] + dp[k+1][j] + sum(freq[i..j]) } (i ≤ k ≤ j)
• 初始化：dp[i][i] = freq[i]，空子树 dp[i][i-1] = 0

核心Java实现

矩阵链乘

import java.util.Arrays;

/**
 * 矩阵链乘：区间DP经典问题
 * 给定矩阵维度数组，求最少乘法次数及最优分割顺序
 */
public class MatrixChainMultiplication {

    /**
     * 计算矩阵链乘的最少标量乘法次数
     * @param dims 维度数组，矩阵Ai的维度为 dims[i-1] x dims[i]
     * @return 最少乘法次数
     */
    public static int minMultiplications(int[] dims) {
        int n = dims.length - 1; // 矩阵数量
        // dp[i][j] = 计算Ai...Aj的最少乘法次数
        int[][] dp = new int[n][n];
        // split[i][j] = Ai...Aj的最优分割点k
        int[][] split = new int[n][n];

        // 初始化：单个矩阵的乘法次数为0
        for (int i = 0; i < n; i++) {
            dp[i][i] = 0;
        }

        // 按区间长度从小到大填表（len=2表示两个矩阵相乘）
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                dp[i][j] = Integer.MAX_VALUE;

                // 枚举分割点k：在Ak和Ak+1之间分割
                for (int k = i; k < j; k++) {
                    // 代价 = 左子链代价 + 右子链代价 + 合并代价
                    int cost = dp[i][k] + dp[k + 1][j]
                             + dims[i] * dims[k + 1] * dims[j + 1];
                    if (cost < dp[i][j]) {
                        dp[i][j] = cost;
                        split[i][j] = k;
                    }
                }
            }
        }

        System.out.println("最少乘法次数: " + dp[0][n - 1]);
        System.out.print("最优加括号方式: ");
        printOptimalParens(split, 0, n - 1);
        System.out.println();

        // 打印DP表
        System.out.println("\nDP表:");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (j < i) {
                    System.out.print("    -");
                } else {
                    System.out.printf(" %5d", dp[i][j]);
                }
            }
            System.out.println();
        }

        return dp[0][n - 1];
    }

    /**
     * 递归打印最优加括号方式
     */
    private static void printOptimalParens(int[][] split, int i, int j) {
        if (i == j) {
            System.out.print("A" + (i + 1));
            return;
        }
        System.out.print("(");
        printOptimalParens(split, i, split[i][j]);
        printOptimalParens(split, split[i][j] + 1, j);
        System.out.print(")");
    }

    public static void main(String[] args) {
        // 示例：6个矩阵，维度分别为 30x35, 35x15, 15x5, 5x10, 10x20, 20x25
        int[] dims = {30, 35, 15, 5, 10, 20, 25};
        System.out.println("矩阵维度序列: " + Arrays.toString(dims));
        System.out.println("矩阵链: A1(30x35), A2(35x15), A3(15x5), A4(5x10), A5(10x20), A6(20x25)");
        System.out.println();
        minMultiplications(dims);
    }
}

最优二叉搜索树

import java.util.Arrays;

/**
 * 最优二叉搜索树：区间DP经典问题
 * 给定有序键的搜索频率，构造期望搜索代价最小的BST
 */
public class OptimalBinarySearchTree {

    /**
     * 计算最优BST的期望搜索代价
     * @param keys 有序键数组
     * @param freq 对应键的搜索频率
     * @return 最小期望搜索代价
     */
    public static double optimalBST(int[] keys, int[] freq) {
        int n = keys.length;
        // dp[i][j] = 键i到j构成的最优BST的期望搜索代价
        double[][] dp = new double[n][n];
        // root[i][j] = 键i到j构成的最优BST的根节点索引
        int[][] root = new int[n][n];
        // prefixSum[i] = freq[0] + freq[1] + ... + freq[i-1]
        double[] prefixSum = new double[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + freq[i];
        }

        // 初始化：单个键的BST
        for (int i = 0; i < n; i++) {
            dp[i][i] = freq[i];
            root[i][i] = i;
        }

        // 按区间长度从小到大填表
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                dp[i][j] = Double.MAX_VALUE;

                // 计算freq[i..j]的和（作为当前子树所有节点的深度+1的额外代价）
                double sumFreq = prefixSum[j + 1] - prefixSum[i];

                // 枚举根节点r
                for (int r = i; r <= j; r++) {
                    // 左子树代价（若r=i则左子树为空，代价为0）
                    double leftCost = (r > i) ? dp[i][r - 1] : 0;
                    // 右子树代价（若r=j则右子树为空，代价为0）
                    double rightCost = (r < j) ? dp[r + 1][j] : 0;

                    double totalCost = leftCost + rightCost + sumFreq;
                    if (totalCost < dp[i][j]) {
                        dp[i][j] = totalCost;
                        root[i][j] = r;
                    }
                }
            }
        }

        System.out.println("最小期望搜索代价: " + String.format("%.2f", dp[0][n - 1]));
        System.out.println("\n最优BST结构:");
        printTree(keys, root, 0, n - 1, 0);

        return dp[0][n - 1];
    }

    /**
     * 递归打印BST结构
     */
    private static void printTree(int[] keys, int[][] root, int i, int j, int depth) {
        if (i > j) return;
        int r = root[i][j];
        String indent = "  ".repeat(depth);
        System.out.println(indent + "键 " + keys[r] + " (深度" + depth + ")");
        if (i <= r - 1) {
            System.out.println(indent + "  左子树:");
            printTree(keys, root, i, r - 1, depth + 1);
        }
        if (r + 1 <= j) {
            System.out.println(indent + "  右子树:");
            printTree(keys, root, r + 1, j, depth + 1);
        }
    }

    public static void main(String[] args) {
        int[] keys = {10, 20, 30, 40, 50};
        int[] freq = {34, 8, 50, 20, 5};
        System.out.println("键: " + Arrays.toString(keys));
        System.out.println("搜索频率: " + Arrays.toString(freq));
        System.out.println();
        optimalBST(keys, freq);
    }
}

区间DP通用框架模板

/**
 * 区间DP通用求解框架
 * 可用于解决石子合并、括号匹配、回文子串等多种区间问题
 */
public class IntervalDPTemplate {

    /**
     * 通用区间DP求解器
     * @param n 区间长度
     * @param costFunction 合并代价函数 cost(i, k, j)
     * @return dp[0][n-1] 表示整个区间的最优解
     */
    public static int solve(int n, TriFunction<Integer, Integer, Integer, Integer> costFunction) {
        int[][] dp = new int[n][n];

        // 初始化单个元素
        for (int i = 0; i < n; i++) {
            dp[i][i] = 0; // 根据具体问题调整初始值
        }

        // 按区间长度递增
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                dp[i][j] = Integer.MAX_VALUE;

                // 枚举分割点
                for (int k = i; k < j; k++) {
                    int cost = dp[i][k] + dp[k + 1][j] + costFunction.apply(i, k, j);
                    if (cost < dp[i][j]) {
                        dp[i][j] = cost;
                    }
                }
            }
        }

        return dp[0][n - 1];
    }

    @FunctionalInterface
    interface TriFunction<A, B, C, R> {
        R apply(A a, B b, C c);
    }

    // 示例：石子合并问题
    public static int stoneMerge(int[] stones) {
        int n = stones.length;
        // 前缀和用于快速计算区间和
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + stones[i];
        }

        // dp[i][j] = 合并stones[i..j]为一堆的最小代价
        int[][] dp = new int[n][n];

        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = i; k < j; k++) {
                    int cost = dp[i][k] + dp[k + 1][j] + (prefix[j + 1] - prefix[i]);
                    dp[i][j] = Math.min(dp[i][j], cost);
                }
            }
        }

        return dp[0][n - 1];
    }

    public static void main(String[] args) {
        // 测试石子合并
        int[] stones = {3, 2, 4, 1};
        System.out.println("石子: " + Arrays.toString(stones));
        System.out.println("最小合并代价: " + stoneMerge(stones));

        // 测试通用框架（矩阵链乘）
        int[] dims = {10, 20, 30, 40};
        int result = solve(dims.length - 1, (i, k, j) -> dims[i] * dims[k + 1] * dims[j + 1]);
        System.out.println("通用框架矩阵链乘结果: " + result);
    }
}

区间DP求解最长回文子序列

/**
 * 最长回文子序列：区间DP的另一经典应用
 * 给定字符串s，求其最长回文子序列的长度
 */
public class LongestPalindromicSubsequence {

    public static int lps(String s) {
        int n = s.length();
        // dp[i][j] = s[i..j]的最长回文子序列长度
        int[][] dp = new int[n][n];

        // 初始化：单个字符是长度为1的回文
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }

        // 按区间长度递增
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;

                if (s.charAt(i) == s.charAt(j)) {
                    // 两端字符相同，可以同时选取
                    dp[i][j] = (len == 2) ? 2 : dp[i + 1][j - 1] + 2;
                } else {
                    // 两端字符不同，取较大的一边
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }

        // 回溯构造回文子序列
        String lps = constructLPS(s, dp);
        System.out.println("字符串: \"" + s + "\"");
        System.out.println("最长回文子序列长度: " + dp[0][n - 1]);
        System.out.println("一个最长回文子序列: \"" + lps + "\"");

        return dp[0][n - 1];
    }

    private static String constructLPS(String s, int[][] dp) {
        int n = s.length();
        StringBuilder left = new StringBuilder();
        StringBuilder right = new StringBuilder();
        int i = 0, j = n - 1;

        while (i <= j) {
            if (s.charAt(i) == s.charAt(j)) {
                left.append(s.charAt(i));
                if (i != j) right.append(s.charAt(j));
                i++; j--;
            } else if (dp[i + 1][j] > dp[i][j - 1]) {
                i++;
            } else {
                j--;
            }
        }

        return left.toString() + right.reverse().toString();
    }

    public static void main(String[] args) {
        lps("character");
        lps("bbbab");
        lps("agbdba");
    }
}

复杂度分析

时间复杂度

区间DP的时间复杂度通用公式为 O(n³)：

• 外层循环遍历区间长度：O(n)
• 中层循环遍历区间起点：O(n)
• 内层循环枚举分割点：O(n)

对于特定问题，利用四边形不等式优化或Knuth优化可将时间复杂度降至 O(n²)：

• 四边形不等式优化：若代价函数满足四边形不等式，则最优分割点具有单调性，split[i][j-1] ≤ split[i][j] ≤ split[i+1][j]。
• Knuth优化：适用于满足四边形不等式和区间包含单调性的问题，如最优BST可将复杂度从O(n³)优化到O(n²)。

空间复杂度

标准区间DP需要 O(n²) 的空间存储dp表。若仅需最终答案而不需要回溯路径，可用滚动数组优化到 O(n)。

状态数分析

区间DP的状态数为 n(n+1)/2 = O(n²)，每个状态需要O(n)次转移计算，因此总复杂度为O(n³)。

区间DP的适用场景与模式识别

典型问题特征

当问题具有以下特征时，可考虑使用区间DP：

1. 问题定义在区间上：如字符串子串、数组子区间、矩阵链等。
2. 最优子结构：大区间的最优解可由小区间的最优解组合得到。
3. 合并/分割操作：需要将区间在某点分割，分别求解后再合并。

经典问题清单

填表顺序的重要性

区间DP必须严格按照区间长度从小到大的顺序填表。这是因为计算 dp[i][j] 时，所有长度小于 (j-i+1) 的 dp 值必须已经计算完毕。错误的填表顺序会导致子问题尚未求解就被引用，从而得到错误答案。

总结

区间DP是解决区间划分与合并问题的利器，其核心在于：

1. 状态定义在区间 [i, j] 上：明确状态表示的含义。
2. 枚举分割点：将大区间分解为两个或多个小区间。
3. 按长度递增填表：确保子问题先求解。

通过矩阵链乘和最优二叉搜索树两个经典案例，我们展示了区间DP从状态设计到递推方程再到代码实现的完整流程。掌握区间DP不仅能解决特定问题，更能培养对”分而治之”思想的深刻理解，为学习更复杂的树形DP和状态压缩DP奠定基础。