题目描述

给定一个字符串s，找到其中最长的回文子序列。可以假设s的最大长度为1000。

示例 1:
输入:

“bbbab”
输出:

4
一个可能的最长回文子序列为 “bbbb”。

示例 2:
输入:

“cbbd”
输出:

2
一个可能的最长回文子序列为 “bb”。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

算法

(动态规划) $O(n^2)$

dp[i][j]:表示从i开始到j，最长的回文子序列。
状态转移：
如果s[i] == s[j] 那么就可以构造出以s[i]为开头和s[j]为结尾的回文子序列， 那么dp[i][j] = dp[i + 1][j - 1] + 2;
如果s[i] != s[j] 则不可能构造以s[i]开头同时以s[j]结尾的最长回文子序列。所以dp[i][j] = max(dp[i+1][j], dp[i][j - 1]);

时间复杂度

我们要枚举每个子串，时间复杂度$O(n^2)$

C++ 代码

class Solution {
public:
    static const int N = 1010;
    int dp[N][N];
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        for(int i = 0; i < n; i ++ ) dp[i][i] = 1;//长度为1的回文子序列
        for(int len = 2; len <= n; len ++ )//枚举长度
            for(int i = 0; i + len - 1 < n; i ++ ){//枚举起点
                int l = i, r = i + len - 1;
                if(s[l] == s[r]) dp[l][r] = dp[l + 1][r - 1] + 2;//状态转移
                else dp[l][r] = max(dp[l][r - 1], dp[l + 1][r]);
            }
        return dp[0][n - 1];
    }
};