一个字符串如果从左往右读和从右往左读都一样,那么这个字符串是一个回文串。例如:"abcba"
,"abccba"
。
蒜头君想通过添加字符把一个非回文字符串变成回文串。例如:"trit"
,可以添加一个'i'
变成回文串"tirit"
。请你用程序计算出,对于一个给定的字符串,最少需要添加几个字符,才能变成回文串。
输入格式
第一行输入一个整数 nn,代表字符串的长度。(1 leq n leq 30001≤n≤3000)
第二行输入一个长度为 nn 的字符串。(字符串只包含字母)
输出格式
输出最少需要添加的字符个数,占一行。
样例输入
trit
样例输出
1
把回文串的顺序倒转后,与原串是一样的。</p><p>那么我们只要把给定的字符串顺序倒转与原串求最长公共子序列,再用字符串总长度减去最长公共子序列的长度就是相差的字符个数,也就是答案
#include<bits/stdc++.h> using namespace std; int dp[3005][3005]; int main() { char a[3005]; char b[3005]; scanf("%s",a); int lena=strlen(a); int t=lena-1; for(int i=0; i<lena; i++) b[t--]=a[i]; int ans=0; for(int i=1; i<=lena; i++) { for(int j=1; j<=lena; j++) { if(a[i-1]==b[j-1]) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i-1][j],dp[i][j-1]); } } for(int i=0; i<=lena; i++) { for(int j=0; j<=lena; j++) { ans=max(ans,dp[i][j]); } } cout<<lena-ans<<endl; return 0; }