本系列文章将于2021年整理出版，书名《算法竞赛专题解析》。

前驱教材是：《算法竞赛入门到进阶》(京东 当当 ) 清华大学出版社。

如有建议，请联系：（1）QQ 群，567554289；（2）作者QQ，15512356

1.概念和模板代码

  区间DP¹是常见的DP应用场景。
  经典例子是“石子合并”问题，用这个例子解释区间DP的概念，并给出两种模板代码。

石子合并
题目描述：有n堆石子排成一排，每堆石子有一定的数量。将n堆石子并成为一堆，每次只能合并相邻的两堆石子，合并的花费为这两堆石子的总数。经过n-1次合并后成为一堆，求总的最小花费。
输入：第一行是整数n，表示有n堆石子。第二行有n个数，分别表示这n堆石子的数目。
输出：总的最小花费。
输入样例：
3
2 4 5
输出样例：
17
提示：样例的计算过程是：第一次合并2+4=6；第二次合并6+5=11；总花费6+11=17。

  定义
$dp[i][j]$

dp[i][j]为合并第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
  
$dp[1][n]$

dp[1][n]就是答案。方程中的
$w[i][j]$

w[i][j]表示从第
$i$

i堆到第
$j$

j堆的石子总数。
  按自顶向下的思路分析状态转移方程，很容易理解。计算大区间
$[i, j]$

[i,j]的最优值时，合并它的两个子区间
$[i, k]$

[i,k]和
$[k+1, j]$

[k+1,j]，对所有可能的合并（
$i ≤ k < j$

i≤k<j，即
$k$

k在
$i、j$

i、j之间滑动），返回那个最优的合并。子区间再继续分解为更小的区间，最小的区间
$[i, i+1]$

[i,i+1]只包含两堆石子。
  编程用自底向上递推的方法，先在小区间进行DP得到最优解，然后再逐步合并小区间为大区间。下面给出求
$dp[i][j]$

dp[i][j]的代码，其中包含
$i、j、k$

i、j、k的3层循环，时间复杂度
$O(n^3)$

O(n3)。第一个循环
$j$

j是区间终点，第2个循环
$i$

i是区间起点，第3个循环
$k$

k在区间内滑动。注意，起点
$i$

i应该从
$j-1$

j−1开始递减，也就是从最小的区间
$[j-1, j]$

[j−1,j]开始，逐步扩大区间。
$i$

i不能从
$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都是递增的，更容易理解，推荐使用。其中用了一个辅助变量
$len$

len，它等于当前处理的区间
$[i, j]$

[i,j]的长度。
$dp[i][j]$

dp[i][j]是大区间，它需要从小区间
$dp[i][k]$

dp[i][k]和
$dp[k+1][j]$

dp[k+1][j]转移而来，所以应该先计算出小区间，才能根据小区间算出大区间。
$len$

len就起到了这个作用，从最小的区间
$len = 2$

len=2开始，此时区间
$[i, j]$

[i,j]等于
$[i, i+1]$

[i,i+1]；最后是最大区间
$len = n$

len=n，此时区间
$[i, j]$

[i,j]等于
$[1, n]$

[1,n]。

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(n3)，区间DP常常可以用“四边形不等式”进行优化，把复杂度提升到
$O(n^2)$

O(n2)，详情见前面博文“四边形不等式”。经典例题“石子合并”也在这一篇进行了更详细的讲解。当然，不是所有的区间DP都能这样优化。
  下面给出2个经典例题。请读者在看题解之前，自己思考并写出代码，一定会大有收获。

2. 例题

2.1. hdu 2476

String painter https://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]，表示在区间[
$1, i$

1,i]内转换为B的最少步数。或者更进一步，定义dp[
$i$

i][
$j$

j]，表示在区间[
$i, j$

i,j]内从空白串转换到B时的最少步数。重点是区间[
$i, j$

i,j]两端的字符B[
$i$

i] 和B[
$j$

j]，分析以下两种情况。
  1）若B[
$i$

i] = B[
$j$

j]。第一次刷用B[
$i$

i]把区间[
$i, j$

i,j]刷一遍，这个刷法肯定是最优的。如果分别去掉两个端点，得到2个区间[
$i+1, j$

i+1,j]、[
$i, j-1$

i,j−1]，这2个区间的最小步数相等，也等于原区间[
$i, j$

i,j]的最小步数。例如B[
$i, j$

i,j]=“abbba”，先用”a”全部刷一遍，再刷1次”bbb”，共刷2次。如果去掉第一个”a”，剩下的”bbba”，也是刷2次。
  2）若B[
$i$

i] ≠ B[
$j$

j]。因为两端点不等，至少要各刷1次。用标准的区间操作，把区间分成
$[i, k]$

[i,k]和
$[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("%dn",dp[1][n]); } return 0; } 

（2）从A转换到B
  如何求dp[
$1$

1][
$j$

j]？观察A和B相同位置的字符，分析以下两种情况.
  1）若A[
$j$

j] = B[
$j$

j]。这个字符不用转换，有dp[
$1$

1][
$j$

j] = dp[
$1$

1][
$j-1$

j−1]。
  2）若A[j] ≠ B[j]。仍然用标准的区间DP，把区间分成
$[1, k]$

[1,k]和
$[k+1, j]$

[k+1,j]两部分，枚举最小步数。这里利用了上一步从空白转换到B的结果，当区间
$[k+1, j]$

[k+1,j]内A和B的字符不同时，从A转到B，与从空白串转换到B是等价的。

2.2. hdu 4283

You Are the One https://acm.hdu.edu.cn/showproblem.php?pid=4283
题目描述：n个男孩去相亲，排成一队上场。大家都不想等，排队越靠后越愤怒。每人的耐心不同，用D表示火气，设男孩
$i$

i的火气是D
$_i$

i​，他排在第
$k$

k个时，愤怒值是(
$k-1)*D_i$

k−1)∗Di​。
  导演不想看到会场气氛紧张。他安排了一个黑屋，可以调整这排男孩上场的顺序，屋子很狭长，先进去的男孩最后出来（黑屋就是一个堆栈）。例如，当男孩A排到时，如果他后面的男孩B火气更大，就把A送进黑屋，让B先上场。一般情况下，那些火气小的男孩要多等等，让火气大的占便宜。不过，零脾气的你也不一定吃亏，如果你原本排在倒数第二个，而最后一个男孩脾气最坏，导演为了让这个刺头第一个上场，把其他人全赶进了黑屋，结果你就排在了黑屋的第1名，第二个上场相亲了。
  注意，每个男孩都要进出黑屋。
  对所有男孩的愤怒值求和，求所有可能情况的最小和。
输入：第一行包含一个整数T，即测试用例的数量。对于每种情况，第一行是n（0 <n <= 100），后面n行，整数D
$_1$

1​-D
$_n$

n​表示男孩的火气值（0 <= D
$_i$

i​ <= 100）。
输出：对每个用例，输出最小愤怒值之和。

题解：
  读者可以试试用栈来模拟，非常困难。这是一道区间DP，巧妙地利用了栈的特性。
  定义dp[
$i$

i][
$j$

j]，表示从第
$i$

i个人到第
$j$

j个人，即区间[
$i, j$

i,j]的最小愤怒值之和。
  由于栈的存在，这一题的区间[
$i, j$

i,j]的分割点
$k$

k比较特殊。分割时，总是用区间[
$i, j$

i,j]的第一个元素
$i$

i把区间分成两部分，让
$i$

i第
$k$

k个从黑屋出来上场相亲，即第
$k$

k个出栈。根据栈的特性：若第一个元素
$i$

i第
$k$

k个出栈，则第二到
$k-1$

k−1个元素肯定在第一个元素之前出栈，第
$k+1$

k+1到最后一个元素肯定在第
$k$

k个之后出栈²。

  例如，5个人排队序号是1、2、3、4、5。如果要第1（
$i$

i=1）个人第3（
$k$

k=3）个出场，那么栈的操作是这样：1进栈、2进栈、3进栈、3出栈、2出栈，1出栈。2号、3号在1号之前出栈，1号第3个出栈，4号5号在1号后面出栈。
  分割点
$k$

k（1≤ k≤j-i+1）把区间划分成了两段，即dp[
$i+1$

i+1][
$i+k-1$

i+k−1]和dp[
$i+k$

i+k][
$j$

j]。dp[
$i$

i][
$j$

j]的计算分为三部分：
  （1）dp[
$i+1$

i+1][
$i+k-1$

i+k−1]。原来
$i$

i后面的
$k-1$

k−1个人，现在排到
$i$

i前面了。
  （2）第
$i$

i个人往后挪了
$k-1$

k−1个位置，愤怒值加上D[
$i$

i]*(
$k-1$

k−1)。
  （3）dp[
$i+k$

i+k][
$j$

j] +
$k*(sum[j] – sum[i+k-1]$

k∗(sum[j]−sum[i+k−1])。第k个位置后面的人，即区间[
$i+k, j$

i+k,j]的人，由于都在前
$k$

k个人之后，相当于从区间的第1个位置往后挪了
$k$

k个位置，所以整体愤怒值要加上
$k*(sum[j]-sum[i+k-1])$

k∗(sum[j]−sum[i+k−1])。其中
$sum[j]=sum_{i=1}^jD_i$

sum[j]=∑i=1j​Di​，是1~j所有人D值的和，
$sum[j] – sum[i+k-1]$

sum[j]−sum[i+k−1]是区间[
$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/