区间DP入门
例题:Educational Codeforces Round 61 (Rated for Div. 2) F题
题目链接:http://codeforces.com/contest/1132/problem/F
题目大意:
给你一个只含小写字母的字符串,每次只能删除一段含有一样字母的区间,问最少删多少次,才能删除整个字符串
解题思路:
(第一次做区间dp 所以记录详细点 适合新手)
我们用dp[ i ][ j ]代表把区间 i 到 j 完全删除需要的次数
状态转移方程
- if(s[ i ] == s[ j ]) dp[ i ][ j ] = dp[i+1][j-1]+1; (两头一样,我们把中间的消去,只剩下两头了,再消一次就好了)
- if(s[ i ] != s[ j ]) dp[ i ][ j ] =min(dp[ i+1 ][ j ],dp[ i ][ j-1 ])+1;(两头不一样,左端单独消去或者右端单独消去)
- 枚举区间i,j中的点,dp[ i ][ j ] = min(dp[ i ][ j ],dp[ i ][ k ] + dp[ k ][ j ] - 1);
前两个状态呢,比较容易得到,但是这两个状态只解决了一半的问题。
我们先来看如何实现这两个状态,首先,我们做dp,根据dp数组的意义,
- 所有 i > j 的dp值为0(区间在 i < x < j )
- 当i = j 时,dp[ i ][ j ]=1(区间内就一个数)
如图 5X5
而根据刚才初步推出来的状态转移方程,我们知道dp[ i ][ j ]要么等于黄色格子+1,要么等于两个蓝色格子最小值+1;
所以,我们根据已知条件和状态转移方程就可以把dp数组填满
当然 我们得要斜着填 如下图 (因为每一个dp值是由其左下方、左边、下边、的值得到的)
//斜着遍历
for(int c=1;c<n;c++){//共n-1轮
for(int i=1,j=c+1;i<=n&&j<=n;i++,j++){
//i代表行 j代表列
}
}
}
好,那么这是前两个状态转移,看似解决了问题,但是还有一种特殊情况没被解决;
比如: abaca
根据我们的状态转移方程2 第一个和第五个字符一样,所以dp[ 1 ][ 5 ] = dp[ 2 ][ 4 ] +1=4
但是其实答案是3(用两步消掉 b c ,一步消除所有的a)
为了解决这种状态,我们在区间i j内枚举每一个点为k,dp[ i ][ j ] = min(dp[ i ][ j ],dp[ i ][ k ] + dp[ k ][ j ] - 1);
正常的话 dp[ i ][ j ] 是等于 dp[ i ][ k ] + dp[ k ][ j ] - 1的 如 abc 或 aba
但是当 特殊情况时 如 aaa 那么dp[ i ][ k ] + dp[ k ][ j ] - 1 得到的值是小于dp[ i ][ j ]的,才是答案。
AC代码:
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
using namespace std;
const int maxn=1e3+7;
int dp[maxn][maxn];
char s[maxn];
int n;
int main(){
scanf("%d",&n);
scanf("%s",s+1);
for(int i=1;i<=n;i++)dp[i][i]=1;
for(int c=1;c<n;c++){
for(int i=1,j=c+1;i<=n&&j<=n;i++,j++){
if(s[i]==s[j])dp[i][j]=dp[i+1][j-1]+1;
else dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1;
for(int k=i;k<=j;k++){
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]-1);
}
}
}
printf("%d\n",dp[1][n]);
return 0;
}