区间dp之最长回文子序列
作者:
巷港
,
2022-03-25 10:08:05
,
所有人可见
,
阅读 183
密码脱落
注意题意的转化,题目求解一个回文串至少去掉几个字符会变成当前串,等价与当前串至少增加几个字符会变成回文串。
再转化一步,求解当前串中的最长回文子序列的长度,当前串的长度减去最长回文子序列的长度就是需要添加的字符个数
#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
const int N = 1010;
int f[N][N];
char s[N];
int main()
{
scanf("%s",s+1); //从下标为1读入
int n=strlen(s+1);
for (int len=1;len<=n;len++) //先枚举区间长度
{
for (int i=1;i+len-1<=n;i++) //枚举左端点
{
int j=i+len-1; //获得右端点
if (len==1) f[i][j]=1; //区间长度为1,即只有一个字符肯定是回文序列
else
{
f[i][j]=max(f[i+1][j-1],max(f[i][j-1],f[i+1][j]));
if (s[i]==s[j]) f[i][j]=max(f[i][j],f[i+1][j-1]+2);
}
}
}
printf("%d\n",n-f[1][n]);
return 0;
}