【学习笔记】区间dp
NCC79601
2019-05-29 22:54:53
## 例题 [P1880](https://www.luogu.org/problemnew/show/P1880)
# 分析
一堆石子在环上，需要合并成一堆，合并时得到的分数为合并后石子的重量，求得到的最大/最小分数。
这很明显就是个区间$\text{dp}$，只是相对来说如何进行状态转移比较蛋疼。
# 转移方程
用$f[i][j]$表示将$[i,j]$区间内的石子合并之后得到的最大分数，那么就可以枚举断点$k\in[i,j)$，进行状态转移：
$$f[i][j]=\max\ f[i][k]+f[k+1][j]+sum(i,j)$$
然后就可以很明显地注意到，虽然转移方程好写，但是以什么样的顺序来进行转移就比较蛋疼了。如果单纯地枚举$i,j$，然后枚举$k$，那么很可能$f[i][k]$和$f[k+1][j]$是根本还没有计算的状态，那么就没有转移的意义了。
所以换个思想，我们希望的是**从简单到复杂**地考虑，比如第一次转移肯定希望是最开始的两堆石子合并，然后第二次转移就是第一次合并之后的石子和相邻石子合并$\cdots$以此类推。这样一想，很明显地发现我们需要的是$d=(j-i)$这个式子**递增**，也就是应该先枚举$d$，然后枚举$i$，最后根据定义，$j=i+d$，就可以保证每次转移的$f[i][k]$和$f[k+1][j]$都是已经计算过的状态。
---
# 总结
这里强调的就是：**枚举顺序非常重要**！可以按照这个思路考虑：
1. 能否覆盖全状态？
2. 用于转移的状态是否已经确定？
3. 是否修改了已经计算好的状态？
---
# Add
2019-7-11复习了一次区间$\text{dp}$，然后我觉得我的理解更加深刻了。
首先，既然是区间$\text{dp}$，一定要找的就是**区间**。$f[i][j]$描述的是$\left[ i,j\right]$区间，还是两个序列的$[1,i]$和$[1,j]$的对应关系？初始的区间有哪些，它们的值分别是多少？
其次，以什么样的顺序枚举？如果是类似分治的思想，需要用小区间合并得到大区间，那么一定是从$len$开始枚举。否则，两层枚举顺序就没有限制。
最后，怎么样合并信息？有没有额外的变动？最后获得的答案在哪一个区间？
---
## [P2758](https://www.luogu.org/problemnew/show/P2758)
这道题说的是给出替换、插入、删除三种操作，将字符串A变为字符串B，询问需要进行的最少操作次数。（A，B字符串长度不一定相等）
**想不到吧！** 这是个区间$\text{dp}$呢！
考虑之后，我建立的模型是$f[i][j]$表示用A串的$[1,i]$区间变为B串的$[1,j]$区间所需要的最少操作次数。
1. 不需要进行操作，直接赋值。
2. 插入，$f[i][j]=f[i][j-1]+1$。
3. 删除，$f[i][j]=f[i-1][j]+1$。
4. 替换，$f[i][j]=f[i-1][j-1]+1$。
最后，对于上述四种情况取最小值即可。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2010;
char s1[MAXN], s2[MAXN];
int f[MAXN][MAXN], len1, len2;
int main()
{
scanf("%s", s1);
len1 = strlen(s1);
getchar();
scanf("%s", s2);
len2 = strlen(s2);
for(int i = 1; i <= len1; i++)
f[i][0] = i; //全部删除
for(int i = 1; i <= len2; i++)
f[0][i] = i; //全部插入
for(int i = 1; i <= len1; i++)
for(int j = 1; j <= len2; j++)
{
if(s1[i - 1] == s2[j - 1])
f[i][j] = f[i - 1][j - 1];
else
f[i][j] = min(min(f[i - 1][j], f[i][j - 1]), f[i - 1][j - 1]) + 1;
}
printf("%d", f[len1][len2]);
return 0;
}
```
---
## [POJ 2955](poj.org/problem?id=2955)
找出最长的匹配括号子序列，**想不到吧！** 这又是个区间$\text{dp}$！
假设有一个待考虑的区间$[i,j]$，获得它的匹配括号子序列有两种办法：
1. 利用 a => (a) 首尾匹配，那么$f[i][j]=f[i+1][j-1]+1$。
2. 利用 a, b => ab 把它从中间砍断，前后分别考虑，那么$f[i][j]=f[i][k]+f[k+1][j]$。
```cpp
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN = 110;
char s[MAXN];
int T, n, f[MAXN][MAXN];
bool match(char a, char b)
{
return (a == '(' && b == ')') || (a == '[' && b == ']');
}
int main()
{
while(1)
{
memset(f, 0, sizeof(f));
scanf("%s", s);
getchar();
if(s[0] == 'e')
return 0;
n = strlen(s);
for(int len = 2; len <= n; len++)
for(int i = 0, j = i + len - 1; j < n; i++, j++)
{
if(match(s[i], s[j]))
f[i][j] = f[i + 1][j - 1] + 2;
for(int k = i; k < j; k++) //得充分考虑！！
f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j]);
}
printf("%d\n", f[0][n - 1]);
}
return 0;
}
```
---
## [POJ 1651](poj.org/problem?id=1651)
给定一个序列，要从中一直拿数直到只剩两个数，每次拿出去的时候获得一个分数，分数等于拿走的数与它相邻两数之积。使获得分数最小。
实际上这道题难在**建模**。用$f[i][j]$表示$[i,j]$区间拿到**只剩首尾两数**获得的最小分数，考虑一个区间$[i,j]$，如果我把这个区间拿到只剩$a[i],a[k],a[j]\ (i<k<j)$三个数，再把$a[k]$拿掉，获得的分数就很显然了。那么拿到只剩三数这个过程就可以继续分治，最后很轻松就获得了答案。
```cpp
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<stdlib.h>
#include<string.h>
using namespace std;
const int MAXN = 110;
// f[i][j] = min(f[i][k] + f[k][j] + a[k] * a[i] * a[j])
int n, a[MAXN];
int f[MAXN][MAXN];
int main()
{
memset(f, 0x3f, sizeof(f));
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for(int i = 1; i <= n; i++)
f[i][i] = 0;
for(int i = 1; i < n; i++)
f[i][i + 1] = 0;
for(int len = 3; len <= n; len++)
for(int i = 1, j = i + len - 1; j <= n; i++, j++)
for(int k = i + 1; k < j; k++)
f[i][j] = min(f[i][j], f[i][k] + f[k][j] + a[i] * a[k] * a[j]);
printf("%d", f[1][n]);
return 0;
}
```
---
## [LightOJ 1422](lightoj.com/volume_showproblem.php?problem=1422)
有一些衣服，可以套着穿，但是脱了就报废，求最少要多少件衣服才够穿。
这题简单粗暴，只要发现一个区间首尾需要穿的衣服一样，那就可以套在里面穿其他衣服。剩余的常规操作即可。这道题难在如何用莽夫思维简化问题。
```cpp
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN = 110;
int n, c[MAXN];
int f[MAXN][MAXN];
int main()
{
int T, cas = 0;
scanf("%d", &T);
while(T--)
{
cas++;
memset(f, 0x3f, sizeof(f));
scanf("%d", &n);
for(int i = 1; i <= n; i++)
scanf("%d", &c[i]);
for(int i = 1; i <= n; i++)
f[i][i] = 1;
for(int len = 2; len <= n; len++)
for(int i = 1, j = i + len - 1; j <= n; i++, j++)
{
if(c[i] == c[j])
f[i][j] = f[i][j - 1];
for(int k = i; k < j; k++)
if(c[i] == c[k])
f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]);
}
printf("Case %d: %d\n", cas, f[1][n]);
}
return 0;
}
```