区间DP

区间DP

石子合并

原题：蓝桥杯省赛无忧班（C&C++ 组）第 1 期 - 石子合并 - 蓝桥云课 (lanqiao.cn)

给n个石块，需要将所有石块合并为1块，每次合并的花销是两个石块的总重量，每次只能合并相邻的石块。

求合并的最小花销。设 dp{i, j} 为 合并 从 i 到 j 个石块的最小花销，可以得到如下的状态转移方程。 \[ dp[i, j] = \min(dp[i][k] + dp[k+1][j] + sum(i, j) | i <= k < j) \] 其中，k为将 [i, j] 这一列石块合并的中间点。为了得到最优解，我们需要遍历每一个k。

注意：必须要以 [i, j]的区间长度 从小到大遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
cin>>n;
memset(dp, 0x3f3f3f3f , sizeof(dp));
for(int i = 1 ; i <= n ; i ++){
    cin>>prefix[i]
    prefix[i] += prefix[i-1];
    dp[i][i] = 0;
}
for(int i = 2 ; i <= n ; i ++){
    for(int l = 1 ; l+i-1 <= n ; l ++){
        int r = l+i-1;
        for(int k = l ; k < r ; k ++){
            dp[l][r] = min(dp[l][r], dp[l][k] + dp[k+1][r] + prefix[r] - prefix[l-1]);
        }
    }
}
cout<<dp[1][n];

涂色

原题：1.涂色 - 蓝桥云课 (lanqiao.cn)

​ CQOI2007 涂色 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

给一个长度为n的字符串，每个字符代表一种颜色，比如：G代表绿，R代表红。每次涂色可以涂任意长度的区间，这一次的涂色会覆盖上一次的涂色。求最少的涂色次数。

设 dp{i, j} 为 正确涂色 从 i 到 j 个石块的最少次数，得到状态转移方程： \[ \begin{cases} dp[i][j] = min(dp[i-1][j], dp[i][j-1]) &s[i] == s[j] \\ \\ dp[i][j] = min(dp[i][k] + dp[k+1][j] \space|\space i<=k<j ) &s[i] != s[j] \end{cases} \] 对于左右端点相同的情况，当前区间的最少次数等同于删去 左端点/右端点 后仍需的涂色次数；

对于不相同的情况，则需要遍历每一种分解的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
cin>>s;
n = s.length();
memset(dp, 0x3f3f3f3f,sizeof(dp));
for(int i = 0 ; i < n ; i ++) dp[i][i] = 1;
for(int i = 2 ; i <= n ; i ++){
    for(int l = 0 ; l+i-1 < n ; l ++){
        int r = l+i-1;
        if(s[l] == s[r]){
            if(i == 2){ // 注意这里的特判
                dp[l][r] = 1;
            }else{
                dp[l][r] = min(dp[l+1][r], dp[l][r-1]);
            }
        }else{
            for(int k = l ; k < r ; k ++){
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k+1][r]);
            }
        }
    }
}
cout<<dp[0][n-1];

制作回文串

原题：1.制作回文串 - 蓝桥云课 (lanqiao.cn)

给一个长度为n的字符串，字符串有m种不同的字母构成，并给出每种字符插入和删除的花销。

求将这个字符串构造成回文串的最小花销。

设 dp{i, j} 为 构造 从 i 到 j 区间的回文串所需的花销，得到状态转移方程： \[ \begin{cases} dp[i, j] = dp[i+1][j-1] & s[i] == s[j]\\ \\ dp[i, j] = min(dp[i+1][j] + cost[i], dp[i][j-1]+cost[j]) & s[i] != s[j] \end{cases} \] 左右端点相同时，我们跳过两端；

不同时，我们选择删除一个花销较小的；

注意：由于对最终生成的字符串没有要求，插入和删除操作都是相同的，我们选择其中一个较小的即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
cin>>m>>n;
cin>>s;
for(int i = 0 ; i < m ; i ++){
    char c;cin>>c;
    int w1,w2;cin>>w1>>w2;
    cost[int(c)] = min(w1,w2);
}
for(int i = 2 ; i <= n ; i ++){
    for(int l = 0 ; l < n ; l ++){
        int r = l+i-1;
        if(s[l] == s[r]){
            if(i == 2){ // 注意特判
                dp[l][r] = 0;
            }else{
                dp[l][r] = dp[l+1][r-1];
            }
        }else{
            dp[l][r] = min(dp[l][r-1] + cost[int(s[r])], dp[l+1][r] + cost[int(s[l])]);
        }
    }
}
cout<<dp[0][n-1];

石子合并2.0

原题：NOI1995] 石子合并 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这题是一道经典的环形区间DP，与1.0的区别是，末尾的石子也可以和队首的石子合并，相当于把 链 变成了 环 。

另外，这道题还要求同时求出 最大值 和 最小值。

对于 4，5，9，4 这个数组，最后的计算结果可能来自 (4,5,9),4, 也可能来自 (4,5) (9,4)。但对于环状的情况，还可能是 (4,4) (5,9)等，类似的情况无法被考虑。

解决环状区间的办法是 退化为 两个连接的链状区间 来解决。

首先，我们将两个原数组相连，构造出：4 5 9 4, 4 5 9 （末尾的4可以不要）

按原长度划分，可以得到如下四种情况：

dp(1,4) ==>4 5 9 4

dp(2,5) ==>5 9 4 4

dp(3,6) ==>9 4 4 5

dp(4,7) ==>4 4 5 9

我们要做的就是求出所有情况的最值，

但是无需对每一段都做单独的dp，只需要做一次n*2规模的dp，然后取值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// 前缀和
cin>>n;
for(int i = 1 ; i <= n ; i ++){
    cin>>prefix[i];
    prefix[i+n] = prefix[i];
}
for(int i = 1 ; i <= n*2 ; i ++){
    prefix[i] += prefix[i-1];
}
// 最小值
memset(dpMin, inf, sizeof(dpMin));
for(int i = 1 ; i < n*2 ; i ++) dpMin[i][i] = 0;
for(int i = 2 ; i <= n ; i ++){
    for(int l = 1 ; l+i-1 < n*2 ; l ++){
        int r = l+i-1;
        for(int k = l ; k < r ; k ++){
            dpMin[l][r] = min(dpMin[l][r], dpMin[l][k] + dpMin[k+1][r] + prefix[r] - prefix[l-1]);
        }
    }
}
min_ = inf;
for(int i = 1 ; i < n ; i ++){
    min_ = min(min_, dpMin[i][i+n-1]);
}
//最大值
for(int i = 2 ; i <= n ; i ++){
    for(int l = 1 ; l+i-1 < n*2 ; l ++){
        int r = l+i-1;
        for(int k = l ; k < r ; k ++){
            dpMax[l][r] = max(dpMax[l][r], dpMax[l][k] + dpMax[k+1][r] + prefix[r] - prefix[l-1]);
        }
    }
}
for(int i = 1 ; i < n ; i ++){
    max_ = max(max_, dpMax[i][i+n-1]);
}
cout<<min_<<"\n"<<max_;

能量项链

原题：1.能量项链 - 蓝桥云课 (lanqiao.cn)

题目很复杂，不解释了

这题和石子合并类似，区别累加的数字是一个乘积。

状态转移方程如下： \[ dp[i, j] = max(dp[i][k] + dp[k+1][j] + v[i]*v[k+1]*v[j+1]) \] 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
cin>>n;
for(int i = 1 ; i <= n ; i ++){
    cin>>v[i];
    v[i+n] = v[i];
}
for(int i = 2 ; i <= n ; i ++){
    for(int l = 1 ; l+i-1 < n*2 ; l ++){
        int r = l+i-1;
        for(int k = l ; k < r ; k ++){
            dp[l][r] = max(dp[l][r], dp[l][k] + dp[k+1][r] + v[l]*v[k+1]*v[r+1]);
        }
    }
}
for(int i = 1 ; i < n ; i ++){
    ans = max(ans, dp[i][i+n-1]);
}
cout<<ans;

最短编辑距离

求最短编辑距离，也叫“近似串匹配”问题

模板题：P2758 编辑距离 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
cin>>s1>>s2;
l1 = s1.length(); s1 = " " + s1;
l2 = s2.length(); s2 = " " + s2;
//初始化边界
for(int i = 0; i <= l1; i ++) dp[i][0] = i;
for(int i = 0; i <= l2; i ++) dp[0][i] = i;

for(int i = 1; i <= l1; i ++){
    for(int j = 1; j <= l2; j ++){
        if(s1[i] == s2[j]){
            dp[i][j] = dp[i-1][j-1];//跳过
        }else{
            dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1);//插入，删除
            dp[i][j] = min(dp[i][j],dp[i-1][j-1] + 1);//修改
        }
    }
}
cout<<dp[l1][l2]<<endl;

模板+路径回溯

CAIP 2022 RC-u4 变牛的最快方法

这里问的是把任意一种动物的图像变成牛的方法…… 比如把一只鼠的图像变换成牛的图像。方法如下：

  • 首先把屏幕上的像素点进行编号；
  • 然后把两只动物的外轮廓像素点编号按顺时针记录下来；
  • 用最少的变换次数将鼠的轮廓变成牛的 —— 这里仅允许对鼠的轮廓进行 3 钟操作：
  1. 插入一个像素编号
  2. 删除一个像素编号
  3. 更改一个像素编号

输入格式

输入分别在两行中给出两种动物的轮廓像素点编号，编号为 (0,106] 区间内的整数，允许重复。轮廓以编号 −1 结尾，这个编号不算在轮廓内。题目保证每种动物的轮廓包含不超过 1000 个像素点。

输出格式

在第一行中输出从第一只动物变换成第二只动物需要的最少变换次数。

在第二行中顺次描述对第一只动物轮廓的每个像素所作的操作：

  • 如果这个像素被删除，则在对应位置输出 0
  • 如果这个像素被改变，则在对应位置输出 1
  • 如果这个像素不变，则在对应位置输出 2
  • 如果这个像素前面或者后面插入了一个像素，则在插入的位置输出 3

答案可能不唯一，输出任何一种可能的解都可以。行首尾和数字间均无空格。

输入样例

1
2
13 5 6 20 2 20 1 13 9 20 3 28 3 34 6 25 233 -1
3 5 6 20 6 20 3 5 9 3 9 20 3 6 6 25 233 -1

输出样例

1
2
8
122212112023121222

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
while(cin>>a1[++l1]){
    if(a1[l1] == -1) break;
}l1--;
while(cin>>a2[++l2]){
    if(a2[l2] == -1) break;
}l2--;

for(int i = 0 ; i <= l1 ; i ++){
    pre[i][0] = make_pair(i-1,0);
    dp[i][0] = i;
    op[i][0] = 0;
}
for(int i = 0 ; i <= l2 ; i ++){
    pre[0][i] = make_pair(0,i-1);
    dp[0][i] = i;
    op[0][i] = 3;
}

//删除 0 改变 1 不变 2 插入 3	
for(int i = 1 ; i <= l1 ; i ++){
    for(int j = 1 ; j <= l2 ; j ++){
        int add = dp[i][j-1] + 1; // 3
        int del = dp[i-1][j] + 1; // 0
        int rpl = dp[i-1][j-1] + (a1[i] != a2[j]); //1 ; 2
        int min_ = min(add,min(del,rpl));
        if(min_ == add){
            dp[i][j] = add;
            pre[i][j] = make_pair(i,j-1);
            op[i][j] = 3;
        }else if(min_ == del){
            dp[i][j] = del;
            pre[i][j] = make_pair(i-1,j);
            op[i][j] = 0;
        }else{
            dp[i][j] = rpl;
            pre[i][j] = make_pair(i-1,j-1);
            op[i][j] = a1[i] == a2[j] ? 2:1;
        }
    }
}
cout<<dp[l1][l2]<<endl;
int x = l1, y = l2;
stack<int> ans;
while(x > 0|| y > 0){
    ans.push(op[x][y]);
    pair<int,int> back = pre[x][y];
    x = back.first, y = back.second;
}
while(!ans.empty()){
    cout<<ans.top();ans.pop();
}
笔记 > 动态规划
#动态规划
区间DP
https://czwcugb.github.io/算法/动态规划/区间DP/
作者
ChenZhiwei
发布于
2025年1月12日
许可协议