重拾 DP（一）：区间类 DP 和划分类 DP

__biu_biu_biu__ · 2026-07-06 21:31:23 · 算法·理论

零、写在前面

最近几场比赛总会被 DP 干爆，我深深的认识到了自己的 DP 能力与做其他类型的题目的能力相差甚远，为了让 CSP2026 考出一个好成绩，我决定重新学习 DP。

那么就让我们一起重新回顾 DP 以及它的奇技淫巧。

一、区间 DP

区间 DP 的复杂度一般为 O(n^3)，但是可以用四边形不等式优化到 O(n^2)，这个后面在讲。

一般来说，如果一个题的范围无法支持 n\ge 10^4，则这个题一般不是区间 DP。

区间 DP 的定义很简单，一般就是 dp_{i,j} 表示区间 [i,j] 的贡献。

区间 DP 的转移一般有两种：一种是枚举单个断点，还有一种是枚举两个断点。

对于枚举一个断点的情况，相当于两个段合并起来需要用的最小代价，转移为 dp_{i,j}=dp_{i,k}+dp_{k,j}+f(i,k,j) 或者 dp_{i,j}=dp_{i,k}+dp_{k+1,j}+f(i,k,j)。

对于枚举两个断点的情况，相当于就是相当于在一段内截取一个子段，然后剩下两个部分会产生一定的贡献，这种题目一般会在删除子段时剩下的会拼到一起的题目背景下出现，转移为 dp_{i,j}=dp_{i,l}+dp_{r,j}+f(i,l,r,j)，此时的复杂度为 O(n^4)。

对于枚举两个断点的情况，会有一下几种特殊情况：

• 在子段两边截取相同的长度：dp_{i,j}=dp_{i+k,j-k}+dp_{i,i+k-1}+dp_{j-k+1,j}+f(i,j,k)；
• 在子段中间截取 x 长度的子段 dp_{i,j}=dp_{i,k}+dp_{k+x+1,j}+f(i,j,k)；

在转移的过程中，我们不能按枚举左端点再枚举右端点的顺序来进行，因为会出现 dp_{i,j} 需要计算但转移中的 dp_{k,j} 还未计算的问题。所以我们需要按长度从小到大遍历，再遍历起点，才能使得转移不漏且过程中的值均已求出。

for(len=1;len<=n;len++){
  for(i=1;i+len-1<=n;i++){
    int j=i+len-1;
    //此时[i,j]就是需要去计算的区间
  }
}

区间 DP 的题目的转移难点一般在 f 函数的定义上，下面我们举几个例题进行分析：

1、P1775 石子合并（弱化版）

有 n 堆石子，第 i 堆有 a_i 个，合并 i 堆 和 j 堆的代价是 a_i+a_j，每次只能合并相邻两堆，求合并为一堆的最小代价，1\le n\le 300。

考虑 dp_{i,j} 表示将第 i\sim j 堆合并为一堆时的答案。

我们思考要合并为一堆的前提条件是只剩了两堆，由于你合并过程是连续的（即不会存在合并了 i 和 i+2 堆却没有 i+1 堆的情况）所以我们可以枚举断点：将 i\sim k 堆和 k+1\sim j 堆合并后，在合并新的两堆。所以我们得到转移式：dp_{i,j}=\min\limits_{i\le k< j} dp_{i,k}+dp_{k+1,j}+\sum\limits_{i\le x\le j}a_x。

时间复杂度 O(n^4)，可以使用前缀和优化，最终时间复杂度 O(n^3)。

2、P3102 [USACO14FEB] Secret Code S

定义一次加密操作为将字符串 S 的一个前缀或一个后缀加到 S 前面或者后面。求加密若干次（至少 1 次）后字符串为 S 的不同操作序列的个数，答案模 2014，1\le n\le 100。

考虑 dp_{i,j} 表示加密 S_{i\sim j} 的方案数。

我们分析 S_{i\sim j} 是怎么得来的：

• 没有经过任何操作，方案数为 1；
• 添加了一个前缀 T，则这个前缀 T 一定是 S-T 的前缀或者后缀，方案数为 \sum dp_{k,j}，其中 k 要满足 S_{i\sim k-1}=S_{k\sim 2k-i-1} 或 S_{i\sim k-1}=S_{j+i-k+1\sim j}。
• 添加了一个后缀 T，则这个后缀 T 一定是 S-T 的前缀或者后缀，方案数为 \sum dp_{i,k}，其中 k 要满足 S_{k+1\sim j}=S_{i\sim i+j-k-1} 或者 S_{k+1\sim j}=S_{2k+1-j\sim k}。

所以我们有转移 dp_{i,j}=1+\sum\limits_{S_{i\sim k-1}=S_{k\sim 2k-i-1}\lor S_{i\sim k-1}=S_{j+i-k+1\sim j}} dp_{k,j}+\sum\limits_{S_{k+1\sim j}=S_{i\sim i+j-k-1}\lor S_{k+1\sim j=S_{2k+1-j\sim k}}} dp_{i,k}。

如果你直接暴力匹配可以做到 O(n^4)，在 n=100 的情况下勉强通过。

当然匹配也可以使用哈希算法，可以做到 O(n^3)。

3、P3146 [USACO16OPEN] 248 G

你可以将两个相邻且相等的元素 a_{i},a_{i+1} 合并为一个元素 a_i+1，求最后可能出现的最大整数。n\le 248。

考虑 dp_{i,j} 表示数 i\sim j 可以合并得到的最大整数。

但是这个东西会很不好合并，因为你根本无法确定你 i\sim j 中的最大值在头、中间还是结尾，这样的话你是无法合并的。

所以我们可以钦定 dp_{i,j} 表示 i\sim j 合并到只剩一个数时的最大整数。如果无法合并到一个数，则 dp_{i,j}=0。

所以这样我们就比较方便转移了：dp_{i,j}=\max\limits_{dp_{i,k}=dp_{k+1,j}>0} dp_{i,k}+1，否则 dp_{i,j}=0。

4、P4170 [CQOI2007] 涂色

每次可以将颜色涂一段，要求将模板涂成指定颜色的最小步数。1\le |S| \le 50。

考虑 dp_{i,j} 表示将 i\sim j 染成目标颜色的指定颜色的最小步数。

首先，我们染色区间省步数的方案一定是将一些颜色相同的区间一起染了，这个东西有一个前提：及不存在多个交叉的像这样省步数的区间染色，则我们相当于找最外层的区间，将其染色来减少染色步数，对于中间被染上的错误颜色，就相当于未染色考虑。

这个步骤相当于如果 s_i=s_j，则 dp_{i,j}=\min(dp_{i+1,j}+dp_{i,j-1})，否则 dp_{i,j}=dp_{i,k}+dp_{k+1,j}。这样一定可以不重不漏的枚举。

时间复杂度 O(n^3)。

5、P2466 [SDOI2008] Sue 的小球

有 n 个点，第 i 个点初始在 (x_i,y_i)，每秒下落 v_i 的时间，你一开始在 x_0，每秒可以走 1 的距离，如果你在某个点的正下方，则可以获得这个点此时高度的价值，如果一个点的高度为负的，则这个点就消失了。你需要在获得所有点的情况下，获得的最大价值为多少，答案乘 10^{-3} 后输出，1\le n\le 1000。

由于获得点的价值不需要消耗时间，所以在三个点 l,x,r 满足 l \le x\le r 的时候，你肯定会按照 l\to x\to r 或者 r\to x\to l 的顺序去接。也就是说，你不会在有点可以获得价值的时候不获得，但不代表你不会去走回头路。

我们考虑按 x 排序，然后考虑 dp_{i,j} 表示将点 i\sim j 接完后能产生的最大价值。

但这样的话你是无法转移的，因为你根本不知道你现在在哪里，怎么走到下一个位置。

根据我们发现的性质，你是不会在 l\le x\le r 的时候停留在 x 的，我们扩展一下，发现对于点 [l,r]，我们接完这些点一定只会停留在 l 或 r 上。

所以我们可以升维，变成 dp_{i,j,0/1} 表示在接完点 i\sim j 后停留在点 i 或点 j 的位置。

此时我们有另一个问题：你的贡献产生是需要依靠时间的，但是如果你的区间 DP 在加一个时间维度显然会爆炸，所以我们可以采用一种类似费用提前计算的方式，每走一步额外增加你其他点落下的损耗，因为你这些点一定会接，所以贡献在哪里计算都无影响。

那么 dp_{i,j,0} 可以由 i+1 点或 j 号点到达，所以有 dp_{i,j,0}=\min(dp_{i+1,j,0}+(x_{i+1}-x_i)\times (sum_{1,i-1}+sum_{j+1,n}),dp_{i+1,j,1}+(x_j-x_i)\times (sum_{1,i-1}+sum_{j+1,n}))。

同理，dp_{i,j,1}=\min(dp_{i,j-1,0}+(x_{j}-x_i)\times (sum_{1,i-1}+sum_{j+1,n}),dp_{i+1,j,1}+(x_j-x_{j-1})\times (sum_{1,i-1}+sum_{j+1,n}))。