1. 全栈程序员必看首页

Palindrome 回文

全栈程序员-站长 • • 未分类 • 阅读 1

Palindrome 回文PalindromePr thatis astringreadi Youaretowrit givenastring determinesth

Palindrome

As an example, by inserting 2 characters, the string “Ab3bd” can be transformed into a palindrome (“dAb3bAd” or “Adb3bdA”). However, inserting fewer than 2 characters does not produce a palindrome.

题目大意：输入一个数字，代表字符串的长度，输入一个字符串，判断最少插入多少个字符能使其变为回文串（正序与反序相同）。

题解代码:

#include 
     #include 
     #define Max(a,b) a>b?a:b int main() { 
    int i,j,n,dp[2][5005]; char str[5005],str2[5005]; while(~scanf("%d",&n)) { 
    getchar(); gets(str); memset(dp,0,sizeof(dp)); for(i = 0,j = n-1; str[i]!='\0'; i++,j--) { 
    str2[i] = str[j]; } for(i = 0; str[i]!='\0'; i++) { 
    for(j = 0; str2[j]!='\0'; j++) { 
    if(str[i] == str2[j]) { 
    dp[(i+1)%2][j+1] = dp[i%2][j]+1; } else { 
    dp[(i+1)%2][j+1] = Max(dp[i%2][j+1],dp[(i+1)%2][j]); } } } printf("%d\n",n-dp[n%2][n]); } return 0; }

hncu2021acm1—1005

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/228157.html原文链接：https://javaforall.net

赞 (0)
0 0

关于作者

全栈程序员-站长的头像

全栈程序员-站长

133.5K 文章
3 粉丝
本网站汇聚当前互联网主流语音，持续更新，欢迎关注公众号“全栈程序员社区”
上一篇 2026年3月16日 下午7:41
下一篇 2026年3月16日 下午7:41


相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号