问题描述

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

本题可以直接利用最长公共子序列求得，但时间复杂度不好，所以我们还是用动态规划解决。

利用最长公共子序列

回文序列的正序和反序完全相同，所以我们可以将原序列 s 反序，得到一个新的序列 s' ，然后对这两个序列求最长公共子序列，其结果即为最长回文子序列。

暴力递归

回文序列是关于中心对称的，所以直觉告诉我们应该从序列的两边开始往内逐一检查，于是先大胆设计出函数原型：

int process(const string &str, int left, int right);

具体的解决思路几乎和最长公共子序列（解法三）完全类似：

如果 str[left] == str[right] ，则最终结果中一定包含这两个字符，所以直接加 2，然后缩小范围继续检查。

如果 str[left] != str[right] ，则分为两种情况：

str[left] 在 [left, right-1] 范围上有相同字符：
str[right] 在 [left+1, right] 范围上有相同字符：
内部范围即不存在 str[left]，也不存在 str[right]

int process(const string &str, int left, int right)
{
    if(left > right)
        return 0;
    if(left == right)
        return 1;
    if(str[left] == str[right])
        return 2 + process(str, left + 1, right - 1);
    int case1 = process(str, left + 1, right);
    int case2 = process(str, left, right - 1);
    //case3为process(str, left+1, right-1),而它不可能比case1和case2大,故直接忽略
    return std::max(case1, case2);
}
int longestPalindromeSubseq(string s)
{
    return process(s, 0, s.length() - 1);
}

动态规划

由上面的暴力递归可看出依赖关系如下：

又因为 left > right 时返回 0 ，所以只需要填表的右上部分：

代码如下：

int help(const string &str, int left, int right, const vector<vector<int>> &dp)
{
    if(left > right)
        return 0;
    if(left == right)
        return 1;
    return dp[left][right];
}
int longestPalindromeSubseq(string s)
{
    vector<vector<int>> dp(s.length(), vector<int>(s.length(), 0));
    //left-row,right-col
    for(int c = 0; c < s.length(); c++)
    {
        for(int r = 0; r < s.length() - c; r++)
        {
            //dp[r][r+c]才是我们实际遍历的位置,斜着遍历
            if(s[r] == s[c+r])
            {
                dp[r][c+r] = 2 + help(s, r+1, c+r-1, dp);
                continue;
            }
            dp[r][c+r] = std::max(help(s, r+1, c+r, dp) ,help(s, r, c+r-1, dp));
        }
    }
    return dp[0][s.length()-1];
}

help 用来处理填表时的越界情况。注意代码是如何进行斜向遍历的。