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

{% hint style="info" %}
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])
{% endhint %}

```cpp
// 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];
}
```

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

```cpp
// 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];
}
```

{% hint style="info" %}
這題和5. Longest Palindromic Substring還有647. Palindromic Substrings有點類似。這題是subsequence，那兩題是substring。
{% endhint %}

{% content-ref url="5.-longest-palindromic-substring" %}
[5.-longest-palindromic-substring](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/dynamic-programming/5.-longest-palindromic-substring)
{% endcontent-ref %}

{% content-ref url="647.-palindromic-substrings" %}
[647.-palindromic-substrings](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/dynamic-programming/647.-palindromic-substrings)
{% endcontent-ref %}