最长回文子序列

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

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：

输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。

示例 2：

输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。

提示：

• 1 <= s.length <= 1000
• s 仅由小写英文字母组成

题解:

class Solution {
public:
//dp[i][j]表示从i到j的s的最长子序列
//s[i]!=s[j]: dp[i][j]=dp[i+1][j-1]
//s[i]==s[j]: i==j dp[i][j]=1 || j-i==1 dp[i][j]=2 ||j-i>1 dp[i][j]=dp[i+1][j-1]+2
//同样更新时候 i从大到小,j从小到大
    int longestPalindromeSubseq(string s) {
        if(s.size()==1) return 1;
        vector<vector<int>> dp(s.size(),vector(s.size(),1));
        //初始化
       // for(int i=0;i<s.size(); ++i) dp[i][i]=1; //这一句可以省略
        for (int i = s.size() -1; i>=0; i--){
            for (int j = i; j <s.size(); j++){
                if(s[i]!=s[j]) dp[i][j]=max(dp[i][j-1],dp[i+1][j]); //这里不是dp[i+1][j-1]
                else{
                    if(j-i==1) dp[i][j]=2;
                    else if(j-i>1) dp[i][j]=dp[i+1][j-1]+2;
                }
            }
        }
        return dp[0][s.size()-1];
    }
};