题解 | #最长回文子序列#

思路：

题目的主要信息：

找到给定串中的最长回文子序列的长度
子序列不同于字串，不要求字符全部相邻
回文序列是指这个序列无论从左读还是从右读都是一样的

方法一：递归（超时）
性质：一个字符串的最长回文子序列等于该字符串与其逆序的最长公共子序列。
具体做法：
我们可以利用上述性质，构造字符串s的逆序字符串rs，然后递归寻找两个字符串的最长公共子序列。对于下标为n-1的s与rs，若是此时两个字符相等，那么子问题就是n-2了，若是不相等，任意一个往前移一个下标作为子问题，找二者的最大值。

class Solution {
public:
    int recursion(int i, int j, string s, string rs){
        if(i == -1 || j == -1)
            return 0;
        int res = 0;
        if(s[i] == rs[j])
            res = recursion(i - 1, j - 1, s, rs) + 1; //找到一个，递归两者都收缩下标
        else
            res = max(recursion(i - 1, j, s, rs), recursion(i, j - 1, s, rs)); //选取一个最大值
        return res;
    }
    int longestPalindromeSubSeq(string s) {
        int n = s.length();
        string rs = "";
        for(int i = n-1; i >= 0; i--) //逆转字符串s
            rs += s[i];  
        return recursion(n - 1, n - 1, s, rs);
    }
};

复杂度分析：

时间复杂度： $O(2^n)$ ，最坏情况是一个二叉树型的递归
空间复杂度： $O(n)$ ，递归栈最大深度与记录逆序字符串rs的空间

方法二：动态规划
具体做法：
这类最长的子xx的问题，我们一般都可以通过动态规划来做。
我们建立一个辅助二维数组dp， $dp[i][j]$ 表示字符串下标 $i$ 到下标 $j$ 的最长的回文子序列的长度，一旦构建好了这个二维数组，我们只需要返回 $dp[0][n-1]$ 即可。
首先初始化，数组的对角线为1，因为自己到自己。
对于下标 $i$ 、 $j$ ，如果 $s[i]==s[j]$ ,则需要在下标 $i+1$ 到下标 $j-1$ 之间增加2个， $dp[i][j]=dp[i+1][j-1]+2$ ；如果 $s[i]!=s[j]$ ,等于向中间收缩的最大值，则 $dp[i][j]=max(dp[i+1][j],dp[i][j-1])$ ;
遍历两层字符串，从右往左维护dp即可。
图片说明

class Solution {
public:
    int longestPalindromeSubSeq(string s) {
        int n = s.length();
        //dp[i][j]表示字符串下标i到下标j的最长的回文子序列的长度
        vector<vector<int> > dp(n, vector<int>(n, 0));
        for(int i = 0; i < n; i++)//对角线置为1
            dp[i][i] = 1;
        for(int i = n - 2; i >= 0; i--){
            for(int j = i + 1; j < n; j++){  //遍历，状态转移
                if(s[i] == s[j])
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                else
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
        return dp[0][n - 1];
    }
};

复杂度分析：

时间复杂度： $O(n^2)$ ，两层遍历
空间复杂度： $O(n^2)$ ，辅助数组dp