题解 P1435 【回文字串】

· · 题解

额，看到楼下都是用什么LCS之类的...

于是我打算来一个不一样的

首先我们看到此题，显然会想到区间DP，且此题是属于2D/0D问题

所以空间复杂度为n^2,时间复杂度也与n^2同阶

（空间优化：楼下讲清楚了...）

关于DP方程的定义：

定义f[i][j]为第i个字符到第j个字符这一段子串需要插入字符构成回文串的最小值

-1 如果str[i]与str[j]相同，显然可以知道f[i][j]=f[i+1][j-1];

-2 如果...不同，可以通过判断是把字符添加在左边小点还是右边小点，即f[i][j]=min(f[i+1][j],j[i][j-1])+1;

(讲个笑话：我自己“自作聪明”，先找了数据自己跑，然后贴数据的时候好像不挂文件就复制不完,结果我调了半个多小时.....（无奈）

-因为此题我是在内部OJ上做的，所以空间开的不同，此题直接乱开空间（233）就是了

  #include<stdio.h>

#include<algorithm>

using namespace std;

char str[5001];

int f[2][5001];

int main()
{
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    int n;
    scanf("%d",&n);
    scanf("%s",str+1);
    int now=0;
    for(int i=n-1;i>=1;i--)
    {
        for(int j=i+1;j<=n;j++)
        {
            if(str[i]==str[j])
            {
                f[now^1][j]=f[now][j-1];
            }
            else
            {
                f[now^1][j]=min(f[now][j],f[now^1][j-1])+1;
            } 
        }
        now=now^1;
    }
    printf("%d",f[now][n]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}