本系列文章将于2021年整理出版，书名《算法竞赛专题解析》。
前驱教材是：《算法竞赛入门到进阶》(京东 当当 ) 清华大学出版社。
如有建议，请联系：（1）QQ 群，567554289；（2）作者QQ，15512356
文章目录
- 1.概念和模板代码
- 2. 例题
- 2.1. hdu 2476
- 2.2. hdu 4283
- 习题
1.概念和模板代码
区间DP1是常见的DP应用场景。
经典例子是“石子合并”问题，用这个例子解释区间DP的概念，并给出两种模板代码。
石子合并
题目描述：有n堆石子排成一排，每堆石子有一定的数量。将n堆石子并成为一堆，每次只能合并相邻的两堆石子，合并的花费为这两堆石子的总数。经过n-1次合并后成为一堆，求总的最小花费。
输入：第一行是整数n，表示有n堆石子。第二行有n个数，分别表示这n堆石子的数目。
输出：总的最小花费。
输入样例：
3
2 4 5
输出样例：
17
提示：样例的计算过程是：第一次合并2+4=6；第二次合并6+5=11；总花费6+11=17。
定义 d p [ i ] [ j ] dp[i][j] dp[i][j]为合并第i堆到第j堆的最小花费。状态转移方程是：
d p [ i ] [ j ] = m i n { d p [ i ] [ k ] + d p [ k + 1 ] [ j ] + w [ i ] [ j ] } dp[i][j] = min\{dp[i][k] + dp[k + 1][j] + w[i][j]\} dp[i][j]=min{dp[i][k]+dp[k+1][j]+w[i][j]} i ≤ k < j i ≤ k <j i≤k<j
d p [ 1 ] [ n ] dp[1][n] dp[1][n]就是答案。方程中的 w [ i ] [ j ] w[i][j] w[i][j]表示从第 i i i堆到第 j j j堆的石子总数。
按自顶向下的思路分析状态转移方程，很容易理解。计算大区间 [ i , j ] [i, j] [i,j]的最优值时，合并它的两个子区间 [ i , k ] [i, k] [i,k]和 [ k + 1 , j ] [k+1, j] [k+1,j]，对所有可能的合并（ i ≤ k < j i ≤ k < j i≤k<j，即 k k k在 i 、 j i、j i、j之间滑动），返回那个最优的合并。子区间再继续分解为更小的区间，最小的区间 [ i , i + 1 ] [i, i+1] [i,i+1]只包含两堆石子。
编程用自底向上递推的方法，先在小区间进行DP得到最优解，然后再逐步合并小区间为大区间。下面给出求 d p [ i ] [ j ] dp[i][j] dp[i][j]的代码，其中包含 i 、 j 、 k i、j、k i、j、k的3层循环，时间复杂度 O ( n 3 ) O(n^3) O(n3)。第一个循环 j j j是区间终点，第2个循环 i i i是区间起点，第3个循环 k k k在区间内滑动。注意，起点 i i i应该从 j − 1 j-1 j−1开始递减，也就是从最小的区间 [ j − 1 , j ] [j-1, j] [j−1,j]开始，逐步扩大区间。 i i i不能从 1 1 1开始递增，那样就是从大区间到小区间了。
for(int i=1; i<=n; i++) //n：石子堆数
dp[i][i] = 0; //初始化
for(int j=2; j<=n; j++) // 区间[i,j]的终点j，i<j<=n
for(int i=j-1;i>=1;i--) { // 区间[i,j]的起点i
dp[i][j]=INF; //初始化为极大值
for(int k=i;k<j;k++) //大区间[i,j]从小区间[i,k]和[k+1,j]转移而来
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + w[i][j]);
}
下面给出另外一种写法，它的 i 、 j 、 k i、j、k i、j、k都是递增的，更容易理解，推荐使用。其中用了一个辅助变量 l e n len len，它等于当前处理的区间 [ i , j ] [i, j] [i,j]的长度。 d p [ i ] [ j ] dp[i][j] dp[i][j]是大区间，它需要从小区间 d p [ i ] [ k ] dp[i][k] dp[i][k]和 d p [ k + 1 ] [ j ] dp[k+1][j] dp[k+1][j]转移而来，所以应该先计算出小区间，才能根据小区间算出大区间。 l e n len len就起到了这个作用，从最小的区间 l e n = 2 len = 2 len=2开始，此时区间 [ i , j ] [i, j] [i,j]等于 [ i , i + 1 ] [i, i+1] [i,i+1]；最后是最大区间 l e n = n len = n len=n，此时区间 [ i , j ] [i, j] [i,j]等于 [ 1 , n ] [1, n] [1,n]。
区间DP的第2种代码（模板）for(int i=1; i<=n; i++)
dp[i][i] = 0;
for(int len=2; len<=n; len++) //len：区间[i,j]的长度，从小区间扩展到大区间
for(int i=1; i<=n-len+1; i++){ // 区间起点i
int j = i + len - 1; // 区间终点j，i<j<=n
dp[i][j] = INF;
for(int k=i; k<j; k++)
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + w[i][j]);
}
区间DP的优化。上述代码的复杂度是 O ( n 3 ) O(n^3) O(n3)，区间DP常常可以用“四边形不等式”进行优化，把复杂度提升到 O ( n 2 ) O(n^2) O(n2)，详情见前面博文“四边形不等式”。经典例题“石子合并”也在这一篇进行了更详细的讲解。当然，不是所有的区间DP都能这样优化。
下面给出2个经典例题。请读者在看题解之前，自己思考并写出代码，一定会大有收获。
2. 例题
2.1. hdu 2476
String painter http://acm.hdu.edu.cn/showproblem.php?pid=2476
题目描述：给定两个长度相等的字符串A、B，由小写字母组成。一次操作，允许把A中的一个连续子串（区间）都转换为某个字符（就像用刷子刷成一样的字符）。要把A转换为B，问最低操作数是多少?
输入：第一行是字符串A，第二行是字符串B。两个字符串的长度不大于100。
输出：一个表示答案的整数。
输入样例：
zzzzzfzzzzz
abcdefedcba
输出样例：
6
提示：第1次把zzzzzfzzzzz转换为aaaaaaaaaaa，第2次转为abbbbbbbbba，第3次转为abccccccccba…
题解：
这道经典题，能帮助读者深入理解区间DP是如何构造和编码的。
（1）从空白串转换到B
先考虑简单一点的问题：从空白串转换到B。为方便阅读代码，把字符串存储为B[1]~B[n]，不从0开始，编码的时候这样输入：scanf("%s%s", A+1, B+1)。
如何定义DP状态？可以定义dp[ i i i]，表示在区间[ 1 , i 1, i 1,i]内转换为B的最少步数。或者更进一步，定义dp[ i i i][ j j j]，表示在区间[ i , j i, j i,j]内从空白串转换到B时的最少步数。重点是区间[ i , j i, j i,j]两端的字符B[ i i i] 和B[ j j j]，分析以下两种情况。
1）若B[ i i i] = B[ j j j]。第一次刷用B[ i i i]把区间[ i , j i, j i,j]刷一遍，这个刷法肯定是最优的。如果分别去掉两个端点，得到2个区间[ i + 1 , j i+1, j i+1,j]、[ i , j − 1 i, j-1 i,j−1]，这2个区间的最小步数相等，也等于原区间[ i , j i, j i,j]的最小步数。例如B[ i , j i, j i,j]=“abbba”，先用"a"全部刷一遍，再刷1次"bbb"，共刷2次。如果去掉第一个"a"，剩下的"bbba"，也是刷2次。
2）若B[ i i i] ≠ B[ j j j]。因为两端点不等，至少要各刷1次。用标准的区间操作，把区间分成 [ i , k ] [i, k] [i,k]和 [ k + 1 , j ] [k+1, j] [k+1,j]两部分，枚举最小步数。
下面是hdu 2476的代码，其中“从空白串转换到B”的代码完全套用了“石子合并”问题的编码。
#include <bits/stdc++.h>
using namespace std;
char A[105],B[105];
int dp[105][105];
const int INF = 0x3f3f3f3f;
int main() {
while(~scanf("%s%s", A+1, B+1)){ //输入A, B
int n = strlen(A+1);
for(int i=1;i<=n;i++)
dp[i][i]=1; //初始化
//先从空白串转换到B
for(int len=2; len<=n; len++)
for(int i=1; i<=n-len+1; i++){
int j = i + len-1;
dp[i][j] = INF;
if(B[i] == B[j]) //区间[i, j]两端的字符相同B[i] = B[j]
dp[i][j] = dp[i+1][j]; //或者 = dp[i][j-1])
else //区间[i, j]两端的字符不同B[i] ≠ B[j]
for(int k=i; k<j; k++)
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]);
}
//下面从A转换到B
for(int j=1; j<=n; ++j){
if(A[j] == B[j])
dp[1][j] = dp[1][j-1]; //字符相同不用转
else
for(int k=1; k<j; ++k)
dp[1][j] = min(dp[1][j], dp[1][k] + dp[k+1][j]);
}
printf("%d\n",dp[1][n]);
}
return 0;
}
（2）从A转换到B
如何求dp[ 1 1 1][ j j j]？观察A和B相同位置的字符，分析以下两种情况.
1）若A[ j j j] = B[ j j j]。这个字符不用转换，有dp[ 1 1 1][ j j j] = dp[ 1 1 1][ j − 1 j-1 j−1]。
2）若A[j] ≠ B[j]。仍然用标准的区间DP，把区间分成 [ 1 , k ] [1, k] [1,k]和 [ k + 1 , j ] [k+1, j] [k+1,j]两部分，枚举最小步数。这里利用了上一步从空白转换到B的结果，当区间 [ k + 1 , j ] [k+1, j] [k+1,j]内A和B的字符不同时，从A转到B，与从空白串转换到B是等价的。
2.2. hdu 4283
You Are the One http://acm.hdu.edu.cn/showproblem.php?pid=4283
题目描述：n个男孩去相亲，排成一队上场。大家都不想等，排队越靠后越愤怒。每人的耐心不同，用D表示火气，设男孩 i i i的火气是D i _i i，他排在第 k k k个时，愤怒值是( k − 1 ) ∗ D i k-1)*D_i k−1)∗Di。
导演不想看到会场气氛紧张。他安排了一个黑屋，可以调整这排男孩上场的顺序，屋子很狭长，先进去的男孩最后出来（黑屋就是一个堆栈）。例如，当男孩A排到时，如果他后面的男孩B火气更大，就把A送进黑屋，让B先上场。一般情况下，那些火气小的男孩要多等等，让火气大的占便宜。不过，零脾气的你也不一定吃亏，如果你原本排在倒数第二个，而最后一个男孩脾气最坏，导演为了让这个刺头第一个上场，把其他人全赶进了黑屋，结果你就排在了黑屋的第1名，第二个上场相亲了。
注意，每个男孩都要进出黑屋。
对所有男孩的愤怒值求和，求所有可能情况的最小和。
输入：第一行包含一个整数T，即测试用例的数量。对于每种情况，第一行是n（0 <n <= 100），后面n行，整数D 1 _1 1-D n _n n表示男孩的火气值（0 <= D i _i i <= 100）。
输出：对每个用例，输出最小愤怒值之和。
题解：
读者可以试试用栈来模拟，非常困难。这是一道区间DP，巧妙地利用了栈的特性。
定义dp[ i i i][ j j j]，表示从第 i i i个人到第 j j j个人，即区间[ i , j i, j i,j]的最小愤怒值之和。
由于栈的存在，这一题的区间[ i , j i, j i,j]的分割点 k k k比较特殊。分割时，总是用区间[ i , j i, j i,j]的第一个元素 i i i把区间分成两部分，让 i i i第 k k k个从黑屋出来上场相亲，即第 k k k个出栈。根据栈的特性：若第一个元素 i i i第 k k k个出栈，则第二到 k − 1 k-1 k−1个元素肯定在第一个元素之前出栈，第 k + 1 k+1 k+1到最后一个元素肯定在第 k k k个之后出栈2。
例如，5个人排队序号是1、2、3、4、5。如果要第1（ i i i=1）个人第3（ k k k=3）个出场，那么栈的操作是这样：1进栈、2进栈、3进栈、3出栈、2出栈，1出栈。2号、3号在1号之前出栈，1号第3个出栈，4号5号在1号后面出栈。
分割点 k k k（1≤ k≤j-i+1）把区间划分成了两段，即dp[ i + 1 i+1 i+1][ i + k − 1 i+k-1 i+k−1]和dp[ i + k i+k i+k][ j j j]。dp[ i i i][ j j j]的计算分为三部分：
（1）dp[ i + 1 i+1 i+1][ i + k − 1 i+k-1 i+k−1]。原来 i i i后面的 k − 1 k-1 k−1个人，现在排到 i i i前面了。
（2）第 i i i个人往后挪了 k − 1 k-1 k−1个位置，愤怒值加上D[ i i i]*( k − 1 k-1 k−1)。
（3）dp[ i + k i+k i+k][ j j j] + k ∗ ( s u m [ j ] − s u m [ i + k − 1 ] k*(sum[j] - sum[i+k-1] k∗(sum[j]−sum[i+k−1])。第k个位置后面的人，即区间[ i + k , j i+k, j i+k,j]的人，由于都在前 k k k个人之后，相当于从区间的第1个位置往后挪了 k k k个位置，所以整体愤怒值要加上 k ∗ ( s u m [ j ] − s u m [ i + k − 1 ] ) k*(sum[j]-sum[i+k-1]) k∗(sum[j]−sum[i+k−1])。其中 s u m [ j ] = ∑ i = 1 j D i sum[j]=\sum_{i=1}^jD_i sum[j]=∑i=1jDi，是1~j所有人D值的和， s u m [ j ] − s u m [ i + k − 1 ] sum[j] - sum[i+k-1] sum[j]−sum[i+k−1]是区间[ i + k , j i+k, j i+k,j]内这些人的D值和。
代码完全套用“石子合并”的模板。其中DP方程给出了两种写法，对照看更清晰。
for(int len=2; len<=n; len++)
for(i=1;i<=n-len+1;i++) {
j = len + i - 1;
dp[i][j] = INF;
for(int k=1;k<=j-i+1;k++) //k：i往后挪了k位。这样写容易理解
dp[i][j] = min(dp[i][j], dp[i+1][i+k-1] + D[i]*(k-1)
+ dp[i+k][j] + k*(sum[j]-sum[i+k-1])); //DP方程
//for(int k=i;k<=j;k++) //或者这样写。k是整个队伍的绝对位置
// dp[i][j] = min(dp[i][j], dp[i+1][k] + D[i]*(k-i)
+ dp[k+1][j] + (k-i+1)*(sum[j]-sum[k]));
}
习题
邝斌带你飞“区间DP”：https://vjudge.net/contest/77874#overview
力扣的DP题目：https://leetcode-cn.com/circle/article/NfHhXD/
区间DP、树形DP、状态压缩DP、数位DP这些名词，可能是中国算法竞赛选手创造的。在英文网站上可以这样搜索对应的英文：区间DP，DP over intervals；树形DP，DP on trees；状态压缩DP，DP on subsets。 ↩︎
这里有个图解：https://blog.csdn.net/weixin_41707869/article/details/99686868 ↩︎
