1. 题目源地址：http://poj.org/problem?id=1159
2. 题目大意：题目就是给你一个字符串，问你添加最少几个字符之后字符串变成回文字符串。
求给出的字符串和逆序的字符串的最长公共子序列，用总长度减去这个最长公共子序列的长度就是答案了。
注意：本题3 <= N <= 5000，若直接使用int dp[5005][5005]会导致内存大小超出，具体优化方式可以使用滚动数组，
使用滚动数组的优化可以参考博客：http://blog.csdn.net/lyy289065406/article/details/6648163
本题，我的代码参考了discuss中short dp[5005][5005]水过。
3. 解题代码：
//POJ--1159:Palindrome
#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;
char a[5005],b[5005];
short dp[5005][5005];
int main()
{
int len;
int i,j;
while(cin>>len)
{
for(i=0;i<len;i++)
{
cin>>a[i];
b[len-i-1]=a[i];
}
dp[0][0]=0;
for(i=1;i<=len;i++)
{
for(j=1;j<=len;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]);
}
}
int ans=len-dp[len][len];
cout<<ans<<endl;
}
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/163030.html
