【动态规划】最长回文子序列lps

腾讯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;
    }
 }