目录
题目:
解题思路:
dp分析:
解题代码:
题目:
解题思路:
题目要求的为脱落的种子数(即回文字符中没有对应回文的字符的数量)
我们可以转换成求回文字符串最长回文字符串的长度
dp分析:
解题代码:
#include<iostream>
#include<cstring>
using namespace std;
const int N=1e3+6;
int f[N][N];
int main(){
string s;
cin>>s;
int len=s.length();
for(int i=1;i<=len;i++){//枚举距离大小
for(int j=0;j+i-1<len;j++){//枚举起点
int l=j;
int r=j+i-1;
if(l==r) f[l][r]=1;//当距离只有一行的时候
else{
f[l][r]=max(f[l+1][r],f[l][r-1]);
//这里对于距离i-1的点每次因为上一次已经枚举完成,故可以直接取max
if(s[l]==s[r]) f[l][r]=max(f[l+1][r-1]+2,f[l][r]);
//对于s[l]和s[r]相等的情况
}
}
}
cout<<len-f[0][len-1];
return 0;
}