POJ 3280 区间DP

一个字符串，每插入或者删除一个字符都需要一定的代价，问怎样可以使这个字符串变成一个回文串，且花费最小。

区间DP

当DP到区间[i,j+1]时，我们可以在i-1的位置添加一个str[j+1]字符，或者将在j+1处的字符删除，得到一个新的回文串，而且我们这两步操作都没有借助或者影响区间[i,j]的情况。

因此，那我们就可以将添加或者删除整合在一起，对字符str[j+1]的操作就按照添加和删除中花费最小的一个计算

DP[j][i] = Min(DP[j+1][i]+dis[str[j]], DP[j][i-1]+dis[str[i]]);

if(str[i] == str[j]) DP[j][i] = MIN(DP[j][i],DP[j+1][i-1]);

#include "stdio.h"
#include "string.h"

int dp[2010][2010];

int Min(int a,int b)
{
    if (a<b) return a; else return b;
}
int main()
{
    int n,m,i,j,a,b;
    char ch;
    char str[2010];
    int dis[210];
    while (scanf("%d%d",&n,&m)!=EOF)
    {
        scanf("%s",str);
        while (n--)
        {
            getchar();
            scanf("%c",&ch);
            scanf("%d%d",&a,&b);
            dis[ch]=Min(a,b);
        }
        memset(dp,0,sizeof(dp));

        for (i=1;i<=m;i++)
            for (j=0;j<=m-i;j++)
            {
                a=j; b=j+i-1;
                dp[a][b]=Min(dp[a+1][b]+dis[str[a]],dp[a][b-1]+dis[str[b]]);
                if (str[a]==str[b]) dp[a][b]=Min(dp[a][b],dp[a+1][b-1]);
            }
        printf("%d\n",dp[0][m-1]);
    }
    return 0;
}

POJ 3280 区间DP,布布扣,bubuko.com

POJ 3280 区间DP

原文：http://blog.csdn.net/u011932355/article/details/38298859