题解 P1435 【回文字串】

· · 题解

先看题意，给定一个字符串，求最少插入几个字符变为回文串（区分大小写）？

样例给出的是Ab3bd，插法有

（1）以A为新字符串中心，变为 db3bAb3bd 需插入4个字符串

（2）以b为字符串中心，变为 db3AbA3bd 需插入4个字符串

（3）以3为字符串中心，变为 Adb3bdA 需插入2个字符串

（4）以第二个b为字符串中心，变为 Ab3dbd3ba 需插入4个字符串

（5）以d为字符串中心，变为 Ab3bdb3bA 需插入4个字符

分析一下，会发现这道题实际求的是最长回文子串（字符串内最长的回文串），最后输出 长度-最长回文子串长度 就可以了

下来就是如何求最长回文子串，回文串的定义是：“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。

既然它正着读，反着读都一样，那我就可以从字符串串首和串尾同时搜索相同的字符进行记录，下来找出最长的就可以了。

这样就可以写出这样的伪代码

    if(串首==串尾)
    回文串长度+=（1或2）；  //若串首和串尾为同一个，则++ else +=2  比如只有字符A或者aAc时，因为为同一个字符，则+=1；
    else
    {
        ???；
    }

下来考虑else怎么写，举个例子AAb时候，很显然回文串长度为2，但是该怎么做呢，这就要用到dp的技巧了；

要求AAb中[1][3]的最长回文串，其中[1][2]为最长回文串，加入为bAA则[2][3]为最长回文串。

那么就可以得出,

    if(串首！=串尾)
    {
        那么F[x][y]=max(F[x-1][y]，F[x][y-1]);
        //[X][Y]中最长回文串为[X-1][Y]与[X][Y-1]中的最大值
    }

最后再考虑一下边界，当X==Y时，return 1，想一想为什么 ，然后你就过了这道水题

最后附上AC代码

#include<bits/stdc++.h>
using namespace std;
string a;
int len1;
int f[1001][1001];
int pipei(int l,int r)
{
    if(f[l][r]!=0)
    return f[l][r];
    if(l==r)
    return f[l][r]=1;
    if(l>r)
    return f[l][r]=0;
    if(a[l]==a[r])
    return f[l][r]=pipei(l+1,r-1)+2;
    else
    return f[l][r]=max(pipei(l+1,r),pipei(l,r-1));
}
int main()
{
    cin>>a;
    len1=a.length();
    cout<<len1-pipei(0,len1-1);

    return 0;
}