Part 5.4：区间 DP

引言：从一排石子说起

想象一下，沙滩上有一排 n 堆石子，每堆石子有一定的重量。你的任务是把这些石子合并成一堆。每次合并，你只能选择相邻的两堆石子，合并后的新石子堆重量是原来两堆之和，而合并的成本也是这两堆石子重量之和。你的目标是：找到一个合并顺序，使得总成本最小。

例如，有四堆石子，重量分别为 [4, 1, 1, 4]。

方案一：
1. 合并 (1, 1)，成本 2，石子变为 [4, 2, 4]。
2. 合并 (4, 2)，成本 6，石子变为 [6, 4]。
3. 合并 (6, 4)，成本 10，石子变为 [10]。
4. 总成本 = 2 + 6 + 10 = 18。
方案二：
1. 合并 (4, 1)，成本 5，石子变为 [5, 1, 4]。
2. 合并 (1, 4)，成本 5，石子变为 [5, 5]。
3. 合并 (5, 5)，成本 10，石子变为 [10]。
4. 总成本 = 5 + 5 + 10 = 20。

不同的合并顺序导致了不同的总成本。如何找到那个最小成本呢？这个问题就是经典的石子合并问题，也是区间动态规划 (Interval DP) 的典型应用场景。

为什么区间 DP 如此重要？

面试价值：区间 DP 是 DP 中的一个标准模型，面试中出现频率很高。它考察的是候选人对 DP 问题建模，特别是对子问题划分和迭代顺序的理解能力。
工程价值：区间 DP 的思想可以应用于多种优化问题，如矩阵链式乘法（决定一组矩阵相乘的最佳顺序）、最优二叉搜索树的构建、生物学中的 RNA 二级结构预测等。

本文将以石子合并问题为核心，带你深入理解区间 DP 的精髓，特别是它那与众不同的遍历方式。

背景知识：合并问题的共性

区间 DP 所解决的问题，通常具有以下共性：

线性排列：问题涉及的元素是线性排列的，如一排石子、一个序列、一条链。
相邻合并：操作总是涉及相邻的元素或子区间。
最优子结构：一个大区间 [i, j] 的最优解，可以通过其所有可能的子区间（如 [i, k] 和 [k+1, j]）的最优解来推导。

区间 DP 的核心思想就是：先求解小区间的最优解，然后利用这些解来构建大区间的最优解，最终得到整个区间的最优解。

详细算法原理

1. 算法的“直觉”：最后一次合并

对于石子合并问题，我们不妨逆向思考：无论之前的合并顺序如何，最后一次合并一定是将两堆已经合并好的石子 [i...k] 和 [k+1...j] 合并成 [i...j]。

图示：最后一次合并

[ stone_i, ..., stone_k ]  <-- 合并 -->  [ stone_{k+1}, ..., stone_j ]

为了使总成本最小，我们必须保证在合并 [i...k] 和 [k+1...j] 之前，这两部分内部的合并成本已经分别是它们各自的最小值了。这就是最优子结构。

那么，为了求解区间 [i, j] 的最小合并成本，我们可以尝试所有可能的“分割点” k（i ≤ k < j），计算将 [i, k] 和 [k+1, j] 合并的成本，并取其中的最小值。

Cost(i, j) = min( Cost(i, k) + Cost(k+1, j) + MergeCost(i, j) ) for k from i to j-1。

MergeCost(i, j) 就是将 [i...k] 和 [k+1...j] 这两大堆合并的成本，它等于从 i 到 j 所有石子的重量之和。

2. 严谨原理：状态定义与状态转移方程

状态定义：dp[i][j] 表示合并区间 [i, j] 内所有石子的最小成本。
状态转移方程：
为了求解 dp[i][j]，我们枚举最后一个合并点 k：
**dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum(i, j))，其中 i ≤ k < j。
sum(i, j) 是从 i 到 j 的石子重量之和。为了快速计算 sum，我们可以预处理一个前缀和数组 prefix_sum**。
**初始化 (Base Case)**：
dp[i][i] = 0。因为单个石子堆不需要合并，成本为 0。

3. 关键：遍历顺序

这是区间 DP 最重要、也最容易出错的地方。观察状态转移方程，dp[i][j] 依赖于 dp[i][k] 和 dp[k+1][j]。这些子问题的区间长度都比 [i, j] 的长度要小。

图示：DP 依赖关系
dp[i][j] 依赖于其左边 dp[i][k] 和其下边 dp[k+1][j] 的值。

这意味着，我们必须在计算大区间的 dp 值之前，先计算完所有小区间的 dp 值。

因此，正确的遍历顺序是按照区间长度 len 从小到大进行遍历。

外层循环：len 从 2 到 n（区间长度）。
中层循环：i 从 0 到 n-len（区间起点）。
计算终点：j = i + len - 1。
内层循环：k 从 i 到 j-1（分割点）。

步骤分解 (Step-by-step)

预处理：计算前缀和数组 prefix_sum。
创建 DP 表：创建一个 n x n 的二维数组 dp。
初始化：dp[i][i] = 0 for all i。
外层循环：len from 2 to n。
中层循环：i from 0 to n-len。
**计算 j**：j = i + len - 1。
初始化 dp[i][j] 为一个极大值。
内层循环：k from i to j-1。
状态转移：dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + cost)。
返回结果：dp[0][n-1] 就是最终答案。

动画式案例

stones = [4, 1, 1, 4]
prefix_sum = [0, 4, 5, 6, 10]

1. 初始化 dp 表 (4x4)

dp[i][i] = 0

2. len = 2

i=0, j=1: dp[0][1] = dp[0][0]+dp[1][1]+sum(0,1) = 0+0+5 = 5
i=1, j=2: dp[1][2] = dp[1][1]+dp[2][2]+sum(1,2) = 0+0+2 = 2
i=2, j=3: dp[2][3] = dp[2][2]+dp[3][3]+sum(2,3) = 0+0+5 = 5

3. len = 3

i=0, j=2: sum(0,2)=6
- k=0: dp[0][0]+dp[1][2]+6 = 0+2+6 = 8
- k=1: dp[0][1]+dp[2][2]+6 = 5+0+6 = 11
- dp[0][2] = min(8, 11) = 8
i=1, j=3: sum(1,3)=9
- k=1: dp[1][1]+dp[2][3]+9 = 0+5+9 = 14
- k=2: dp[1][2]+dp[3][3]+9 = 2+0+9 = 11
- dp[1][3] = min(14, 11) = 11

4. len = 4

i=0, j=3: sum(0,3)=10
- k=0: dp[0][0]+dp[1][3]+10 = 0+11+10 = 21
- k=1: dp[0][1]+dp[2][3]+10 = 5+5+10 = 20
- k=2: dp[0][2]+dp[3][3]+10 = 8+0+10 = 18
- dp[0][3] = min(21, 20, 18) = 18

最终答案: dp[0][3] = 18。

Python 实现

import math

def merge_stones(stones):
    """
    使用区间 DP 解决石子合并问题。
    """
    n = len(stones)
    if n <= 1:
        return 0

    # 1. 预处理前缀和
    prefix_sum = [0] * (n + 1)
    for i in range(n):
        prefix_sum[i + 1] = prefix_sum[i] + stones[i]

    def get_sum(i, j):
        return prefix_sum[j + 1] - prefix_sum[i]

    # 2. 创建并初始化 DP 表
    dp = [[0] * n for _ in range(n)]

    # 3. 按区间长度遍历
    for length in range(2, n + 1):
        # 4. 遍历区间起点
        for i in range(n - length + 1):
            # 5. 计算区间终点
            j = i + length - 1
            dp[i][j] = math.inf
            current_sum = get_sum(i, j)
            
            # 6. 遍历分割点
            for k in range(i, j):
                # 7. 状态转移
                cost = dp[i][k] + dp[k + 1][j] + current_sum
                dp[i][j] = min(dp[i][j], cost)

    # 8. 返回结果
    return dp[0][n - 1]

# --- 案例测试 ---
stones = [4, 1, 1, 4]
print(f"最小合并成本是: {merge_stones(stones)}") # 输出: 18

stones2 = [1, 2, 3, 4, 5]
print(f"最小合并成本是: {merge_stones(stones2)}") # 输出: 33

复杂度推导过程

时间复杂度: O(n³)。
- 外层循环 len 遍历 n 次。
- 中层循环 i 遍历 n 次。
- 内层循环 k 遍历 n 次。
- 总共是三层嵌套循环。
空间复杂度: O(n²)。
- 我们需要一个 n x n 的 dp 表。
- 前缀和数组需要 O(n) 的空间。
- 总空间由 dp 表主导。

优势 / 劣势 / 易错点

优势

模式固定：区间 DP 的代码结构非常固定，一旦掌握，可以解决一类问题。
思路清晰：将大区间问题分解为小区间问题的思想很自然。

劣势

复杂度高：O(n³) 的时间复杂度使其不适用于 n 非常大的情况。
不易识别：有些问题需要转化为区间 DP 模型，识别过程有一定难度。

易错点

遍历顺序错误：这是最致命的错误。如果按 i 和 j 直接遍历，会导致计算 dp[i][j] 时所依赖的子问题尚未被计算。必须按区间长度 len 遍历！
边界条件：循环的起止点，特别是 i 和 k 的范围，容易出错。
前缀和计算：sum(i, j) 的计算如果每次都重新求和，会导致时间复杂度上升到 O(n^4)。必须预处理前缀和。

适用场景

区间 DP 适用于所有满足“通过合并相邻元素求解区间最优值”特征的问题。

石子合并 / 木棍切割：经典模型。
矩阵链式乘法：找到 A₁*A₂*...*Aₙ 的最优加括号方式，使得总的标量乘法次数最少。
多边形三角剖分：将一个凸多边形分割成若干个三角形，求最优的分割方案。
最优二叉搜索树：给定一组键和它们的查询频率，构建一棵平均查找时间最短的二叉搜索树。
字符串问题：如“最长回文子序列”也可以用区间 DP 的思想来解决。

总结

区间 DP 是动态规划中一个独特而强大的分支。它通过一种“由内而外”的扩展方式，从最小的区间逐步构建出整个问题的最优解。

本文核心要点

✅ 核心思想：大区间的最优解由其所有子区间的最优解推导而来。
✅ 状态定义：dp[i][j] 表示区间 [i, j] 的最优解。
✅ 状态转移方程：dp[i][j] = min/max (dp[i][k] + dp[k+1][j] + cost)。
✅ 遍历顺序：必须按区间长度 len 从小到大进行遍历，这是区间 DP 的灵魂。
✅ 复杂度：通常是时间 O(n³)，空间 O(n²)。

掌握了区间 DP，你就拥有了解决一类复杂组合优化问题的有力武器。在下一篇文章中，我们将进入一个更有趣的领域——树形 DP，学习如何在树形结构上进行动态规划。

大学算法全体系 > Part 5：动态规划

#算法基础 #动态规划 #DP #区间DP

Part 5.4：区间 DP

https://hjjjkh.github.io/posts/dac28bdb

作者

李国强

发布于

2025年11月15日

许可协议

Part 2.8：二叉搜索树：有序世界的高效查找上一篇

Part 2.7：并查集：高效处理“朋友圈”问题下一篇