Coding Interview Prep · 课时

区间 DP 模式与填表顺序

Q: 「区间 DP 模式与填表顺序」课时是免费的吗？

是的 — 「区间 DP 模式与填表顺序」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。

Q: 「区间 DP 模式与填表顺序」这节课中我会学到什么？

定义区间 DP 状态 dp[i][j]，解释为什么必须按区间长度递增的顺序填表，并在矩阵链乘法上跟踪这一模式。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

Q: 学习 Coding Interview Prep 需要有经验吗？

无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 1 节课，共 4 节。

Q: 「区间 DP 模式与填表顺序」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

Q: 我能在这节 Coding Interview Prep 课中编写并运行代码吗？

能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

定义区间 DP 状态 dp[i][j]，解释为什么必须按区间长度递增的顺序填表，并在矩阵链乘法上跟踪这一模式。

区间 DP 模式与填表顺序 是 CoddyKit 上的免费 Coding Interview Prep 课时。这是第 1 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。

什么是区间 DP？

区间 DP 是一种动态规划模式，其中状态 dp[i][j] 表示跨越索引 i 到 j 的子问题的最优答案。关键思路是先解决较小的区间，再逐步扩展到完整范围。这种模式自然适用于矩阵链乘法、回文分割和气球爆破等问题，因为这些问题的子问题边界就是一个范围的左右端点。

状态定义与基础情况

对于区间 DP，状态是 dp[i][j]，其中 i <= j。基础情况是单元素区间：dp[i][i]。这些情况可以直接解决——例如，单个矩阵的乘法成本为零。两个元素的区间 dp[i][i+1] 通常也有简单的答案。我们按照区间长度递增的顺序填充表格，从长度 1 开始，直到 n。

n = 4
dp = [[0] * n for _ in range(n)]
# Base cases: single elements
for i in range(n):
    dp[i][i] = 0  # length-1 intervals

按递增长度填充

区间 DP 的关键细节是填充顺序。我们必须先计算长度为 L 的所有区间，再计算长度为 L+1 的区间，因为较长区间依赖于较短的子区间。外层循环将区间长度从 2 迭代到 n，中间循环设置左边界 i，然后根据 j = i + L - 1 推导右边界。

n = 5
dp = [[float('inf')] * n for _ in range(n)]
for i in range(n):
    dp[i][i] = 0

for length in range(2, n + 1):      # interval length
    for i in range(n - length + 1): # left boundary
        j = i + length - 1          # right boundary
        for k in range(i, j):       # split point
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j])

矩阵链乘法设置

经典的区间 DP 问题是矩阵链乘法：给定维度为 dims[0..n] 的矩阵，求计算乘积所需的最少标量乘法次数。将矩阵 A(p×q) 与 B(q×r) 相乘需要进行 p*q*r 次运算。dp[i][j] = 将矩阵 i 到 j 相乘的最小成本。分割点 k 决定将序列分成哪两个子链。

def matrix_chain_order(dims):
    n = len(dims) - 1  # number of matrices
    dp = [[0] * n for _ in range(n)]
    
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                cost = dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1]
                dp[i][j] = min(dp[i][j], cost)
    return dp[0][n-1]

print(matrix_chain_order([10, 30, 5, 60]))  # 4500

追踪 DP 表

让我们用维度为 [10, 30, 5, 60] 的矩阵链示例进行追踪，该示例表示三个矩阵：A(10×30)、B(30×5)、C(5×60)。对于 dp[0][2]，我们尝试在 k=0 处分割：dp[0][0] + dp[1][2] + 10×30×60 = 0 + 9000 + 18000 = 27000；也尝试在 k=1 处分割：dp[0][1] + dp[2][2] + 10×5×60 = 1500 + 0 + 3000 = 4500。因此，dp[0][2] = 4500，实现这一结果的方式是先计算 AB。

为什么这种填充顺序有效

计算 dp[i][j] 时，我们会对所有位于 [i, j-1] 中的 k，引用 dp[i][k] 和 dp[k+1][j]。这两个子区间的长度都严格小于 [i, j]。按照长度从小到大的顺序迭代，就能确保所有必需的子区间都在使用前完成计算。这就是区间 DP 填充顺序的基本正确性依据——较短区间始终是较长区间的依赖项。

记忆化自顶向下区间 DP

此外，也可以使用带记忆化的自顶向下方法实现区间 DP。我们编写递归函数 solve(i, j)，使其返回区间 [i, j] 的最优成本，并将结果缓存到字典中。填充顺序会由递归自动处理。自顶向下的方法通常更容易理解，但可能有函数调用开销；对于较大的输入，自底向上方法在实践中更快。

from functools import lru_cache

def matrix_chain_memo(dims):
    n = len(dims) - 1
    
    @lru_cache(maxsize=None)
    def solve(i, j):
        if i == j:
            return 0
        return min(
            solve(i, k) + solve(k+1, j) + dims[i]*dims[k+1]*dims[j+1]
            for k in range(i, j)
        )
    
    return solve(0, n-1)

print(matrix_chain_memo([10, 30, 5, 60]))  # 4500

time 与空间复杂度

区间 DP 有O(n²) 个状态（所有 (i, j) 对），每个状态都会遍历 O(n) 个分割点，因此总体为O(n³) time。DP 表占用O(n²) 空间。对于包含 100 个矩阵的矩阵链，这相当于 1,000,000 次运算，非常可行。这种模式出现在许多困难的 LeetCode 问题中，并且由于其不明显的结构，深受 FAANG 面试青睐。

重建最优 solution

要重建实际的加括号方式（而不仅仅是成本），请存储一个单独的 split[i][j] 表，记录每个状态中取得最小值的 k。然后递归读取这些分割点：reconstruct(i, j) 通过对 [i, split[i][j]] 和 [split[i][j]+1, j] 进行递归，输出最优分组。这种技术适用于所有区间 DP 问题。

def matrix_chain_with_split(dims):
    n = len(dims) - 1
    dp = [[0]*n for _ in range(n)]
    split = [[0]*n for _ in range(n)]
    
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                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
    return dp[0][n-1], split

适用于任何区间 DP 问题的模板

通用区间 DP 模板包含三个部分：(1) 为单个元素初始化基础情况；(2) 按长度递增的顺序循环，并在每个长度下遍历有效的左边界，计算右边界；(3) 对每个区间遍历所有分割点，并应用问题特定的递推关系。不同问题之间唯一变化的是最内层循环中的递推公式。

def interval_dp_template(n, base_cost, split_cost):
    dp = [[float('inf')] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = base_cost(i)  # problem-specific base case
    
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            for k in range(i, j):
                # problem-specific recurrence
                candidate = dp[i][k] + dp[k+1][j] + split_cost(i, k, j)
                dp[i][j] = min(dp[i][j], candidate)
    
    return dp[0][n-1]

常见的区间 DP 问题

使用区间 DP 的问题包括：矩阵链乘法（最小化运算次数）、气球爆破（最大化硬币数）、奇怪的打印机（最小化打印次数）、多边形的最小得分三角剖分以及回文分割 II。它们使用相同的填充顺序框架，但递推关系不同。当问题要求计算一个范围或序列上的最优值，并且该范围或序列可以在任意内部位置分割时，请识别出这种模式。

快速检查

请测试您对本课数据结构 & 算法——编程面试准备相关概念的理解。

课程回顾

本课中您学到了：区间 DP 使用 dp[i][j] 表示一个范围上的最优答案；填充顺序必须按照区间长度递增，以便先计算子区间；以及通用模板的 time 复杂度为 O(n³)，空间复杂度为 O(n²)。接下来，我们将使用这一模式探索最长回文子序列和子串。

常见问题解答