零基础区间DP教程：告别死记硬背，从DFS出发

ZhangChuan1350 · 2026-02-10 12:46:09 · 算法·理论

前言

本文从最原始的 DFS 开始，带你一步步推导出区间 DP 的标准解法。

看完这篇教程后，你会发现：

递归天然就是按区间长度展开的。
f[l][r] 的定义就是 dfs(l, r) 的返回值。
那三个循环的顺序，只是递归顺序的自然翻译。

以洛谷 P1775 石子合并（弱化版）为例，演示如何从 DFS 走到 DP。

你不需要背任何东西，只需要跟我写一次 DFS。

洛谷 P1775 石子合并（弱化版）

题面描述： 有 N 堆石子排成一排，第 i 堆重量为 m_i。每次只能合并相邻的两堆，代价为两堆重量之和。求将所有石子合并成一堆的最小总代价。

Step 1：先别想 DP，想暴力

我们要合并区间 [1,N]。

最后一步一定是：把某两堆合并成一堆，假设两堆之间的分隔点为 k。
但这两堆，其实是由 [1,k] 和 [k+1,N] 各自合并成的一大堆。

所以——只要枚举 k，先合并左边，再合并右边，最后把左右两大堆合并。

这不就是个递归吗？

定义 dfs(l, r) 表示：把区间 [l,r] 合并成一堆的最小代价。

边界：如果 l=r，已经是一堆，代价 0。
否则：

\operatorname{dfs}(l,r)=\min_{k=l}^{r-1}\big[\operatorname{dfs}(l,k)+\operatorname{dfs}(k+1,r)+\operatorname{sum}(l,r)\big]

其中，\operatorname{sum} 是 [l,r] 的重量和（最后合并左右两大堆的代价），由前缀和实现。

如果你对递归分治还不太有画面感，可以想象一棵树：

       [1,4]
      /     \
  [1,2]     [3,4]
   /  \     /   \
[1,1][2,2][3,3][4,4]

这就是 dfs(1,4) 的递归树。
大区间依赖小区间，小区间先算完，大区间才能算——
这个依赖顺序，就是后来递推DP里区间长度从小到大的根源。

这张图的“从左到右、从下往上”的顺序，
就是后来递推 DP 里“区间长度从小到大”的唯一来源。
你不能也无法改变，因为这个递归树本身就是这么长的，我们的任务是翻译，而不是改变。

Step 2：写出这个递归，哪怕它很慢

区间和可以用前缀和 p 快速计算：

\operatorname{sum}(l,r)=p_r-p_{l-1}

区间和如果每次都累加，是 O(n) 的，总复杂度会变成 O(n^4)。
我们需要 O(1) 查询区间和——前缀和就是干这个的。

for (int i = 1; i <= n; ++i) { //预处理前缀和
    p[i] = p[i-1] + m[i];
}
//定义 O(1) 区间和查询函数
int sum(int l, int r) {return p[r] - p[l-1];} //计算前缀和

我们用 m[i] 存储第 i 堆石子重量，p[i] 是前缀和。

把思路翻译成代码，出乎意料地直白。

const int INF = 0x3f3f3f3f;
int dfs(int l, int r) {
    if (l == r) return 0;
    int res = INF;
    for (int k = l; k < r; ++k) {
        int cost = dfs(l, k) + dfs(k + 1, r) + sum(l, r);
        res = min(res, cost);
    }
    return res;
}

恭喜——你已经写出了区间 DP 的代码 v1.0 版本。

剩下的所有事情——记忆化、递推、~~四边形不等式~~ ——
都只是在帮这个递归“续命”，让它在 N=300 时不会爆炸，让它在 N=5000 时还能活

Step 3：让递归跑快一点

我们刚刚写的 DFS 逻辑完全正确，但它有一个致命伤。

❗ 重复计算——递归的阿克琉斯之踵
我们先画出 dfs(1,4) 的递归树：

dfs(1,4)
├─ dfs(1,2)
│  ├─ dfs(1,1)
│  └─ dfs(2,2)
└─ dfs(3,4)
   ├─ dfs(3,3)
   └─ dfs(4,4)

※ 上图仅为 k=2 时的递归路径。实际递归会枚举所有 k，每个 k 都会展开一棵类似的子树。

看起来每个子问题只出现了一次，对吗？

不对。这是一次调用的局部视角。
如果你的程序只算一次 dfs(1,4)，那确实没有重复。

但问题是： 在递归计算过程中，同一个子问题会被不同的大区间反复请求。

举个例子：

计算 dfs(1,5) 时，它的递归树里也会出现 dfs(3,4)。
计算 dfs(2,6) 时，还会出现 dfs(3,4)。 ……

同一个 (l,r)，被成千上万次地重复计算。
这就是重叠子问题——暴力版区间 DP 的命门。

📌 看一个具体的重复
假设我们接下来要计算 dfs(2,5) —— 它的递归树长这样：

            dfs(2,5)
           /        \
     dfs(2,3)       dfs(4,5)
     /  \            /    \
dfs(2,2) dfs(3,4)   ...   // 这里又出现了 dfs(3,4)！

同一个 (3,4)，被 dfs(1,4) 和 dfs(2,5) 重复计算了两次。
当 N 很大时，这种重复会爆炸式增长。

这就是递归慢的根本原因——不是在“分治”，是在“反复造轮子”。

📦 解决方案：把答案记下来，记忆化搜索
就像你做完一道数学题，把答案写在草稿纸角落，下次遇到一模一样的题直接抄。

我们用一个数组 f[l][r] 来存储 dfs(l, r) 的结果。

int mem[305][305];      // 记忆化数组，初始为 -1 表示未计算

int dfs(int l, int r) {
    if (l == r) return 0;
    if (mem[l][r] != -1) return mem[l][r];   // 直接返回已算好的结果

    int res = INF;
    for (int k = l; k < r; ++k) {
        int cost = dfs(l, k) + dfs(k + 1, r) + sum(l, r);
        res = min(res, cost);
    }
    return mem[l][r] = res;   // 记录并返回
}
int main()
{
    memset(mem, -1, sizeof mem); //记忆化数组必须初始化！-1 表示未计算
    //……接下来的代码与 DFS 的一致
    return 0;
}

恭喜——这是区间 DP 的代码 v2.0 版本。

⏱ 现在多快？

每个 (l,r) 只计算一次。
总共有 O(n^2) 个状态，每个状态要枚举 O(n) 个 k。
时间复杂度：O(n^3)，空间复杂度：O(n^2)。

对于 N\leqslant300，这个复杂度绰绰有余——你的代码将在 0.01 秒内跑完。

但如果你和我一样，看那三行循环还是不顺眼：

为什么区间长度要从小到大？
为什么左端点要那样枚举？

别急，Step 4 会把记忆化搜索一字一句地翻译成递推。
你会发现，那三行循环不是规定，是翻译的必然结果。
看完你会发现：原来不是它高冷，是你没见过它的草稿。

Step 4：由递归转向递推

你现在手里有一份记忆化搜索的代码，它已经能 AC，而且思路无比清晰。
但参考书那三行循环，还是像咒语一样横在你心里。

今天我们不做别的，就做一件事： 把记忆化搜索，逐行翻译成递推 DP。

让我们看看记忆化搜索与 DP 的联系：	联系	记忆化搜索（自顶向下）
样式	`dfs(l, r)`	`f[l][r]`
寻找分隔点	`for (int k = l; k < r; ++k)`	`for (int k = l; k < r; ++k)`
子问题	递归调用 `dfs(l, k)` 和 `dfs(k+1, r)`	直接查表 `f[l][k]` 和 `f[k+1][r]`
边界	`if (l == r) return 0;`	`f[i][i] = 0;`
区别	依赖顺序由递归隐式保证	必须按区间长度从小到大显式枚举

首先，如果一个区间的长度为 1，即该区间只包含一个数，那么不用合并（即代价为 0）。
由此，自然而然诞生出 \forall~i\leqslant N,~f_{i,i}=0。

接着，我们要枚举子区间的长度，设长度为 \mathrm{len}，则显然有 2\leqslant \mathrm{len}\leqslant N，因为长度为 1 的区间已经被考虑，子区间的长度又不可能超过 N。

然后，考虑子区间的左端点，设左端点位置为 l，则有 1\leqslant l\leqslant N-\mathrm{len}+1。
当初，我在这里也有点迷糊：左端点不小于 1 好理解，但 (N-\mathrm{len}+1) 是个啥玩意儿？
可以这样理解：左端点 l 的最大值 =N-\mathrm{len}+1，因为此时右端点 r=l+\mathrm{len}-1=N，刚好顶到末尾。否则 l 再大就超出数组范围了。

再考虑子区间右端点，设右端点的位置为 r，则有 r=l+\mathrm{len}-1。
用左端点的例子亦可明白。

最后，考虑子区间 [l,r] 在哪里分隔，假设分隔点位置为 k，则显然有 l\leqslant k<r，这样分出来的两个子子区间分别为 [l,k] 与 [k+1,r]。
为什么 k 可以等于 l，却必须严格小于 r 呢？
答：从分出来的两个子子区间可知，如果 k\leqslant r，则第二个子子区间的长度将会是 -1，显然不对。

💡 拓展阅读：另一种等价的写法
有同学可能见过 for (int k = l + 1; k <= r; ++k) 的写法，此时分割出的子区间为 [l, k-1] 和 [k, r]。两种写法本质相同，都能 AC，选择一种你顺手的记住即可。
本文采用第一种，因为它更直观地体现了分割点 k 属于左半区间的语义。
但初学者不建议同时学两种——先吃透一种，另一种自然触类旁通。

考虑状态转移方程：
令 f_{l,r} 表示在子区间 [l,r] 的最小合并代价，则：

若不选当前分割点 k，则 f_{l,r} 维持原样，即 f_{l,r}\leftarrow f_{l,r}。
若选择当前分割点 k，则 f_{l,r} 的值由 [l,k]、[k+1,r] 的最小合并代价之和决定，还要加上当前区间 [l,r] 的所有石子的重量 \operatorname{sum}(l,r)。

综上，可得出 f_{l,r} 的状态转移方程为

f_{l,r}=\min_{k=l}^{r-1}\big[f_{l,k}+f_{k+1,r}+\operatorname{sum}(l,r)\big]

即 [1,N] 的最小合并代价为 f_{1,N}

P1775 的完整代码自然而然地浮现出来：

#include <bits/stdc++.h>
using namespace std;
int n, m[305], p[305], f[305][305];
int sum(int l, int r) {
    return p[r] - p[l - 1];   //计算前缀和
}
int main()
{
    //一定要赋一个极大的值
    memset(f, 0x3f, sizeof f); //因为 0x3f3f3f3f 的每个字节都是 0x3f
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &m[i]);
        p[i] = p[i - 1] + m[i]; //预处理前缀和
        f[i][i] = 0; //区间长度为1，不必合并
    }
    for (int len = 2; len <= n; ++len) { //枚举当前区间长度
        for (int l = 1; l <= n - len + 1; ++l) { //枚举左端点
            int r = l + len - 1; //计算右端点
            for (int k = l; k < r; ++k) {
                f[l][r] = min(f[l][r], f[l][k] + f[k+1][r] + sum(l,r));
            }
        }
    }
    printf("%d", f[1][n]);
    return 0;
}

恭喜——你亲手把“记忆化搜索”翻译成了“递推 DP”。
那三行曾经背不下来的循环，现在是你自己写出来的。

递推的 DP 对比记忆化搜索，优点如下：

避免栈空间溢出导致的 RE。
常数时间更优，虽然总时间复杂度仍为 O(n^3)。
常数空间更优，因为 DP 避免了占用系统栈空间。

:::epigraph[] 谨以此文，献给三个月前初学区间 DP 的自己。
:::

版权声明

:::epigraph[声明] 本文的核心思想、推导过程、代码实现均由本人独立完成。
在撰写过程中，使用了 DeepSeek 对全文的语句通顺度进行润色。 ::: 本文采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

您需遵守下列条件：

署名：您必须给出适当的署名，提供指向本许可协议的链接，并标明是否对原始作品作了修改。您可以用任何合理的方式来署名，但不得以任何方式暗示许可人为您或您的使用背书。
非商业性使用：您不得将本作品用于商业目的。
相同方式共享：如果您再混合、转换或者基于本作品进行创作，您必须基于与原先相同的许可协议分发您贡献的作品。

最后，欢迎各位读者引用本文（需注明文章来源和署名），祝您区间 DP 之路一帆风顺！