LeetCode——Longest Palindromic Subsequence

1. Question

Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000.

Example 1:

Input:

"bbbab"

Output:

4

One possible longest palindromic subsequence is "bbbb".

Example 2:

Input:

"cbbd"

Output:

2

One possible longest palindromic subsequence is "bb".

2. Solution

1. 动态规划。依次求出所有长度的子字符串的最长回文子序列。

2. dp[i][i + j] = max(s[i] == s[i + j] ? dp[i + 1][i + j – 1] + 2 : dp[i + 1][i + j – 1], max(dp[i + 1][i + j], dp[i][i + j – 1])); 其中i表示起点，j表示子字符串长度。

3. Code

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        // dp
        int len = s.length();
        vector<vector<int>> dp(len, vector<int>(len, 1));        for (int j = 1; j < s.length(); j++) {
            for (int i = 0; i < s.length() - j; i++) {
                dp[i][i + j] = max(dp[i + 1][i + j], dp[i][i + j - 1]);
                if (s[i] == s[i + j]) {
                    if (i + 1 <= i + j - 1) {
                        dp[i][i + j] = max(dp[i][i + j], dp[i + 1][i + j - 1] + 2);
                    } else
                        dp[i][i + j] = max(dp[i][i + j], j + 1);
                } else {
                    if (i + 1 <= i + j - 1)
                        dp[i][i + j] = max(dp[i][i + j], dp[i + 1][i + j - 1]);
                }
            }
        }
        return dp[0][s.length() - 1];
    }
};