区间 DP：合并与分割的艺术

一、什么是区间 DP

区间 DP 是在一个区间 [i, j] 上定义状态，通过枚举分割点 k 将大区间拆分为两个小区间来转移的 DP 模型。

核心特征：

状态：dp[i][j] 表示区间 [i, j] 的最优值
转移：枚举分割点 k，dp[i][j] = f(dp[i][k], dp[k+1][j])
遍历顺序：按区间长度从小到大

Mermaid · 渲染中（下方为源码）

graph TD
  A["dp[i][j]"] --> B["dp[i][k]"]
  A --> C["dp[k+1][j]"]
  B --> D["更小区间..."]
  C --> E["更小区间..."]

二、通用模板

// 初始化：长度为 1 的区间
for (int i = 0; i < n; i++) dp[i][i] = baseValue;

// 按长度从小到大枚举
for (int len = 2; len <= n; len++) {
    for (int i = 0; i + len - 1 < n; i++) {
        int j = i + len - 1;
        dp[i][j] = INF;   // 或 0，取决于求 min 还是 max
        for (int k = i; k < j; k++) {
            dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j] + cost);
        }
    }
}

时间：O(n³)，：O(n²)

一、什么是区间 DP

区间 DP 是在一个区间 [i, j] 上定义状态，通过枚举分割点 k 将大区间拆分为两个小区间来转移的 DP 模型。

核心特征：

状态：dp[i][j] 表示区间 [i, j] 的最优值
转移：枚举分割点 k，dp[i][j] = f(dp[i][k], dp[k+1][j])
遍历顺序：按区间长度从小到大

Mermaid · 渲染中（下方为源码）

graph TD
  A["dp[i][j]"] --> B["dp[i][k]"]
  A --> C["dp[k+1][j]"]
  B --> D["更小区间..."]
  C --> E["更小区间..."]

二、通用模板

// 初始化：长度为 1 的区间
for (int i = 0; i < n; i++) dp[i][i] = baseValue;

// 按长度从小到大枚举
for (int len = 2; len <= n; len++) {
    for (int i = 0; i + len - 1 < n; i++) {
        int j = i + len - 1;
        dp[i][j] = INF;   // 或 0，取决于求 min 还是 max
        for (int k = i; k < j; k++) {
            dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j] + cost);
        }
    }
}

时间：O(n³)，：O(n²)

public int maxCoins(int[] nums) {
    int n = nums.length;
    int[] arr = new int[n + 2];
    arr[0] = arr[n + 1] = 1;   // 虚拟边界
    System.arraycopy(nums, 0, arr, 1, n);

    int[][] dp = new int[n + 2][n + 2];
    for (int len = 1; len <= n; len++) {
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            for (int k = i; k <= j; k++) {
                // k 是区间 [i,j] 中最后一个被戳的
                int coins = arr[i - 1] * arr[k] * arr[j + 1];
                dp[i][j] = Math.max(dp[i][j],
                    dp[i][k - 1] + coins + dp[k + 1][j]);
            }
        }
    }
    return dp[1][n];
}

public int mergeStones(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];

    int[][] dp = new int[n][n];
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            dp[i][j] = Integer.MAX_VALUE;
            for (int k = i; k < j; k++) {
                dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j]);
            }
            dp[i][j] += prefix[j + 1] - prefix[i];   // 合并代价
        }
    }
    return dp[0][n - 1];
}

public int longestPalindromeSubseq(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];
    for (int i = 0; i < n; i++) dp[i][i] = 1;

    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            if (s.charAt(i) == s.charAt(j)) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[0][n - 1];
}

public int matrixChainOrder(int[] p) {
    int n = p.length - 1;   // n 个矩阵
    int[][] dp = new int[n][n];

    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; 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] + p[i] * p[k + 1] * p[j + 1];
                dp[i][j] = Math.min(dp[i][j], cost);
            }
        }
    }
    return dp[0][n - 1];
}

信号	示例
"合并相邻元素"	合并石子、戳气球
"在区间上操作"	回文子序列、矩阵链乘
"分割成子区间"	最优 BST、分割回文串
状态是 [i, j] 区间	任何 dp[i][j] 表示区间

优化	条件	效果
四边形不等式	cost 满足单调性	O(n³) → O(n²)
记忆化搜索	状态稀疏	减少无效计算
环形处理	首尾相连	数组翻倍（长度 2n）

区间 DP：合并与分割的艺术

一、什么是区间 DP

二、通用模板

区间DP·石子合并 Interval DP

一、什么是区间 DP

二、通用模板

区间DP·石子合并 Interval DP

三、经典案例

3.1 戳气球（LeetCode 312）

3.2 合并石子

3.3 最长回文子序列

3.4 矩阵链乘法

四、区间 DP 的识别信号

五、优化方向

环形区间 DP

六、面试常见题

七、调试技巧

相关教程