区间DP

早就想写一份关于DP的专题了，可是毕竟太弱，，，，刷得太久了

先来个刷题链接：

bin神带你飞之区间DP

不是对于每个题都分析，分析各个弱会的好了：

1、Light oj 1422 Halloween Costumes

题意：给你n天需要穿的衣服的样式，每次可以套着穿衣服，脱掉的衣服就不能再用了（可以再穿），问至少要带多少条衣服才能参加所有宴会

lightoj1422

int dp[maxn][maxn];
int num[maxn];

int main(){
	//input;
	int t,n,i,j,k,len;
	scanf("%d",&t);
	for(int Case=1;Case<=t;Case++){
		scanf("%d",&n);
		for(i=1;i<=n;i++) scanf("%d",&num[i]);
		memset(dp,0,sizeof(dp));
		for(i=1;i<=n;i++) dp[i][i]=1;
		for(i=n-1;i>=1;i--)
			for(len=2;len+i<=n+1;len++){
				j=i+len-1;
				if (num[i]!=num[i+1]) dp[i][j]=dp[i+1][j]+1;
				else dp[i][j]=dp[i+1][j];
				for(k=i+1;k<=j;k++)
					if (num[k]==num[i])
					dp[i][j]=min(dp[i][j],dp[i+1][k-1]+dp[k][j]);
			}
		printf("Case %d: %d\n",Case,dp[1][n]);
	}
	return 0;
}
/*
	dp[i][j]表示第i到第j最少需要多少衣服
	那么有两种扩展方案：
	1.穿衣服。那么若由后往前更新：
		即：已知dp[i+1][j]推dp[i][j]
	2.脱衣服。与其他的状态进行组合 
*/

2、 poj2955（括号匹配问题）

题意：给你一串()[]括号，要你求出这串括号的最大匹配个数，如'('与')'匹配，为2个，'['与']'匹配，为2个，其他不能匹配.......

POJ2955

思路：dp[i][j]为i到j区间中最大的括号匹配数量

个人偏好记忆化

初始条件有：l==r，l+1==r，分析方案递推有：区间的左和右匹配，区间的左和右不匹配

int dp[maxn][maxn];
char s[maxn];

int GetDp(int l,int r){
	if (dp[l][r]!=-1) return dp[l][r];
	if (l+1==r){
		if ((s[l]=='('&&s[r]==')')||(s[l]=='['&&s[r]==']')) return dp[l][r]=2;
		return dp[l][r]=0;
	}
	if (l==r) return dp[l][r]=0;
	if ((s[l]=='('&&s[r]==')')||(s[l]=='['&&s[r]==']')) dp[l][r]=2+GetDp(l+1,r-1);
	for(int i=l;i<r;i++)
		dp[l][r]=max(GetDp(l,i)+GetDp(i+1,r),dp[l][r]);
	return dp[l][r];
}
int main(){
	//input;
	int n,i,j;
	while(scanf("%s",s+1)){
		if (s[1]=='e') break;
		n=strlen(s+1);
		memset(dp,-1,sizeof(dp));
		printf("%d\n",GetDp(1,n));
	}
	return 0;
}

3、poj3280（推荐）

题意：给你m个字符，其中有n种字符，每种字符都有两个值，分别是增加一个这样的字符的代价，删除一个这样的字符的代价，让你求将原先给出的那串字符变成回文串的最小代价。

POJ3280

这个题首先可以剪枝：添加和删除对应的其实没有区别：如abcb可以添加a（添加在右边）或者删除a（在左边删除），得到的结果其实对其他的状态没有影响，因此在输入时候，添加和删除的情况记录费用最小的就好

dp的思路：dp【i】【j】同样的，同上题的记忆化

但是注意这题的“区间”可递推的地方只有两个：左端点和右端点

这还可以引出另外一类题型：

状态设计如下：dp【i】【j】【0】为区间【i】【j】且停留在左边的时候的最值，dp【i】【j】【1】为区间【i】【j】且停留在右边的时候的最值。。与本题无关。。。

int n,m;
char s[maxm],op[5];
int cost[maxn];
int dp[maxm][maxm];

int GetDp(int l,int r){
	if (dp[l][r]!=-1) return dp[l][r];
	if (l==r) return dp[l][r]=0;
	if (l+1==r){
		if (s[l]==s[r]) return dp[l][r]=0;
		return dp[l][r]=min(cost[s[l]-'a'],cost[s[r]-'a']);
	}
	if (s[l]==s[r]) dp[l][r]=GetDp(l+1,r-1);
	else dp[l][r]=min(GetDp(l+1,r)+cost[s[l]-'a'],GetDp(l,r-1)+cost[s[r]-'a']);
	return dp[l][r];
}

int main(){
	//input;
	int i,j,k,x,y;
	while(scanf("%d%d",&n,&m)!=EOF){
		scanf("%s",s+1);
		for(i=1;i<=n;i++){
			scanf("%s%d%d",op,&x,&y);
			cost[op[0]-'a']=min(x,y);
		}
		memset(dp,-1,sizeof(dp));
		printf("%d\n",GetDp(1,m));
	}
	return 0;
}

POJ又跪了。。。搞得都没有心情写了。。。碎觉碎觉

——————————————————————————————————————————————————

强行一条分界线明天继续

4、poj1141（区间dp记录路径问题）

题意：给出一串括号，要你补上最少的括号使这一串括号都匹配........

思路：dp[i][j]表示从区间i到区间j使其所以括号匹配需要补上的最少括号数

POJ1141

这是我毛毛雨教我做人的一题系列，主要的难度是递归输出方案，其中dp【i】【j】取得最值时，那么需要记录a【i】【j】的分段点为k，于是，就需要递归输出方案：：那么推荐弱的另外一篇博客：

Dp中记录方案递归输出

代码如下：

char c[120];
long f[120][120];
long g[120][120];
long n;
void prt(long l, long r)
{
	if (r == l)
	{
		if ((c[l] == '(') || (c[l] == ')')) printf("()");
		if ((c[l] == '[') || (c[l] == ']')) printf("[]");
		return ;
	}
 	if (g[l][r] == -1)
	{
		if ( (c[l] == '(') && (c[r] == ')') )
		{
			printf("(");
			prt(l + 1, r - 1);
			printf(")");
		}
		if ( (c[l] == '[') && (c[r] == ']') )
		{
			printf("[");
			prt(l + 1, r - 1);
			printf("]");
		}
	}
	else{
		prt(l, g[l][r]);
		prt(g[l][r] + 1, r);
	}

}
void dp()
{
	n = strlen(c);
	memset(f, 127, sizeof(f));
	memset(g, -1, sizeof(g));
	for (long i = 0; i < n; i++)
	{
		f[i][i] = 1;
	}
	for (long l = 2; l <= n; l++)
	{
		for (long i =0; i + l - 1 < n; i++)
		{
			long j = i + l - 1;

			if (((c[i] == '[') && (c[j] == ']')) || ((c[i] == '(') && (c[j] == ')')))
			{
				if (i + 1 == j) f[i][j] =0;
				if (f[i][j] > f[i + 1][j - 1])
				{
					f[i][j] = f[i + 1][j - 1];
				}
			}

			for (long k = i; k < j; k++)
			{
				if (f[i][j] > f[i][k] + f[k + 1][j])
				{
					f[i][j] = f[i][k] + f[k + 1][j];
					g[i][j] = k;
				}
			}
		}
	}
	//cout << f[0][n - 1] << endl;
}
int main()
{
	while (gets(c))
	{
	    if (strlen(c) == 0)
	    {
			printf("\n");
			continue;
	    }
		dp();
		prt(0, n - 1);
		printf("\n");
	}
    return 0;
}

5、poj1651（推荐）

题意：给你一组数字，第一个和最后一个数字不可以取出去，其它任意取出去，当你要取出一个数字时，它有一个代价，这个代价就是与它相邻的两个数的乘积，求除了首位两位数字，把其他数字都取出来，它们的代价之和的最小值........

POJ1651

简单的区间DP题：枚举中间的每个位置即可，思路常规

int num[maxn];
int dp[maxn][maxn];
int i,j,k,t,n,len;

int main(){
	//input;
	while(scanf("%d",&n)!=EOF){
		for(i=1;i<=n;i++) scanf("%d",&num[i]);
		memset(dp,0,sizeof(dp));
		for(i=1;i<n-1;i++)
		for(j=i+2;j<=n;j++)
			dp[i][j]=INF;
		for(i=n-2;i>=1;i--)
		for(len=3;len+i<=n+1;len++){
			j=len+i-1;
			for(k=i+1;k+1<=j;k++)
				dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+num[i]*num[k]*num[j]);
		}
		//for(i=1;i<=n;i++)
		//for(j=1;j<=n;j++)
		//	printf("%d%c",dp[i][j],j==n?'\n':' ');
		printf("%d\n",dp[1][n]);
	}
	return 0;
}

6、poj3661（推荐）

题意：给你一个n,m，n表示有n分钟，每i分钟对应的是第i分钟能跑的距离，m代表最大疲劳度，每跑一分钟疲劳度+1，当疲劳度==m，必须休息，在任意时刻都可以选择休息，如果选择休息，那么必须休息到疲劳度为0，当然，当疲劳度为0的时候也是可以继续选择休息的，求在n分钟后疲劳度为0所跑的最大距离

POJ3661

自己感觉这个题不算是区间dp，而是最简单的DP

dp【i】【j】为第i分钟j点疲劳度时候取得的最大距离，那么最终答案为dp【n】【0】

递推有：dp[i][0]=max(dp[i-1][1],dp[i-1][0]) 当之前的疲劳度为0时，可以选择走或者不走

另外，枚举前一时刻的疲劳度递推得当前的dp值

int n,m;
int num[maxn];
int dp[maxn][maxm];

int main(){
	//input;
	int i,j,k;
	while(scanf("%d%d",&n,&m)!=EOF){
		for(i=1;i<=n;i++) scanf("%d",&num[i]);
		memset(dp,-1,sizeof(dp));
		dp[0][0]=0;
		for(i=1;i<=n;i++){
			dp[i][0]=max(dp[i-1][1],dp[i-1][0]);
			for(j=1;j<=m&&j<=i;j++){
				if (dp[i-1][j-1]!=-1) dp[i][j]=max(dp[i][j],dp[i-1][j-1]+num[i]);
				dp[i][0]=max(dp[i][0],dp[i-j][j]);
			}
		}
		printf("%d\n",dp[n][0]);
	}
	return 0;
}

7、hdu2476(推荐)

给出两串字符，要你将第一串字符变成第二串字符，每次可以改变连续的一个或多个字符，求最少的修改次数