POJ 1159 Palindrome

Description

Input

Output

Sample Input

5
Ab3bd

Sample Output

2

简单的 区间动规，主要是容易MLE。

AC代码如下：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
char a[5005];
short dp[5005][5005];//用short就可以不MLE了
int min(int a,int b)
{
    return a<b?a:b;
}

int main()
{
    int n;
    int ans;
    int i,j;
    while(cin>>n)
    {
        memset(dp,0,sizeof dp);
        cin>>a+1;
        //cout<<a+1;
        for(i=1;i<=n;i++)
        {
            dp[i][i]=0;//i==j时不用补字母
        }
        int len;
        for(len=2;len<=n;len++)
        {
            for(i=1;i<=n-len+1;i++)
            {
                j=i+len-1;
                if(a[i]==a[j])//此时[i,j]需要补字母数等于[i+1,j-1]中所需补的字母
                    dp[i][j]=dp[i+1][j-1];
                else
                {
                    dp[i][j]=min(dp[i][j-1],dp[i+1][j])+1;//此时需要找两个缩小区间的最小值
                }

            }
        }
        cout<<dp[1][n]<<endl;
    }
    return 0;
}

POJ 1159 Palindrome,布布扣,bubuko.com

POJ 1159 Palindrome

原文：http://blog.csdn.net/hanhai768/article/details/37557723