腾讯2016实习笔试编程题
所谓回文字符串，就是一个字符串，从左到右读和从右到左读是完全一样的，比如“aba”、“c”对于一个字符串，可以通过删除某些字符而变成回文字符串，如“cabebaf”，删除'c'、'e'、‘f’后剩下子串“abba”就是回文字符串。要求，给定任意一个字符串，字符串最大长度1000，计算出最长的回文字符串长度。如“cabebaf”的回文串包括“c”、“aba”、“abba”等，最长回文“abba”长度为4。
输入：字符串
输出：最大的回文字符长度。
示例：
输入：cabbeaf
输出：4
基本思路：
设lps(0,n-1)表示下标0~n-1的子串的最长回文子序列的长度。当str[0]==str[n-1]时，lps(0,n-1)=lps(1,n-2)+2;
当str[0]!=str[n-1]时，lps(0,n-1)=max(lps(0,n-2),lps(1,n-1))。
参考代码
#include<bits\stdc++.h>
using namespace std;
const int MAX = 1010;
int dp[MAX][MAX];
int lps(int n,string str){
memset(dp,0,sizeof(dp));
for (int i=0;i<n;++i) dp[i][i]=1;
for (int i=1;i<n;++i){
for (int j=0;j+i<n;++j){
if (str[j]==str[j+i]) dp[j][j+i]=dp[j+1][j+i-1]+2;
else dp[j][j+i]=max(dp[j][j+i-1],dp[j+1][j+i]);
}
}
return dp[0][n-1];
}
int main()
{
string str;
while(cin>>str){
cout<<lps(str.length(),str)<<endl;
}
}
