516. Longest Palindromic Subsequence

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".

dp[i][j]代表string[i...j]中最長的palindromic subsequence長度。先初始化dp[i][i]為1，如果s[i]和s[j]字元相同，最長的palindromic subsequence長度加2，如果字元不同，則從s[i+1...j]和s[i...j-1]之中去找longest palindromic subsequence。 dp state transition: dp[i][j] = dp[i + 1][j - 1] + 2 if s[i] == s[j] Otherwise, dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

// Bottom-Up Dynamic Programming
int longestPalindromeSubseq(string s) { // time: O(n^2); space: O(n^2)
    int n = s.size();
    vector<vector<int> > dp(n, vector<int>(n, 0));
    for (int j = 0; j < n; ++j) {
        dp[j][j] = 1;
        for (int i = j - 1; i >= 0; --i) {
            if (s[i] == s[j]) {
                dp[i][j] = (j - i >= 2 ? dp[i + 1][j - 1] : 0) + 2;
            } else {
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[0][n - 1];
}

Top-down dp利用memoization紀錄已經計算過的組合避免大量重複運算。memo 2D vector存的值是-1代表還沒計算過該種組合，概念跟bottom-up dp類似。

// Top-Down Dynamic Programming
int longestPalindromeSubseq(string s) { // time: O(n^2); space: O(n^2)
    int n = s.size();
    vector<vector<int> > memo(n, vector<int>(n, -1));
    return helper(s, 0, n - 1, memo);
}
int helper(string& s, int start, int end, vector<vector<int> >& memo) {
    if (memo[start][end] != -1) return memo[start][end];
    if (start > end) return 0;
    if (start == end) return 1;
    if (s[start] == s[end]) memo[start][end] = helper(s, start + 1, end - 1, memo) + 2;
    else memo[start][end] = max(helper(s, start + 1, end, memo), helper(s, start, end - 1, memo));
    return memo[start][end];
}

這題和5. Longest Palindromic Substring還有647. Palindromic Substrings有點類似。這題是subsequence，那兩題是substring。

5. Longest Palindromic Substring

647. Palindromic Substrings