題目網址：https://leetcode.cn/problems/longest-palindromic-subsequence/

題意：給一 string s, 找出其中最長的回文 subsequence, 並返回該 subsequence 的長度。

subsequence：不改變 char 順序的情況下, 刪除某些 char 或者不刪除任何 char 形成的一個 sequence。

Solution：

想法：利用 DP

1. 定義狀態：

  • 首先, 會在 s 前先加上一個 #, 代表什麼元素都沒有的狀態
  • dp[i][j]：區間 s[i:j] 中最長回文 subseq 之長度

2. 得到轉移方程：

  • 若 s[i] == s[j], 則取出小區間 s[i + 1][j - 1] + 2
    ➔ dp[i][j] = dp[i + 1][j - 1] + 2
  • 否則, 取 dp[i][j - 1]、dp[i + 1][j] 這兩個小區間中較大者
    ➔ dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])

3. 初始化：

  • dp[i][i]：當區間中只有一個 char 時, 最長回文 subseq 之長度為 1, 其中 1 ≤ i ≤ n
  • 其餘區間之初始值皆設 0
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        const int n = s.size();
        vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));

        for (int i = 1; i <= n; ++i) {
            dp[i][i] = 1;
        }

        s = '#' + s;

        for (int len = 2; len <= n; ++len) { // 區間長度, 從 2 開始（因為 len = 1 已處理）
            for (int i = 1; i + len - 1 <= n; ++i) { // // i 為區間的起始位置
                const int j = i + len - 1; // j 為區間的結束位置
                if (s[i] == s[j]) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);
                }
            }
        }

        return dp[1][n];
    }
};
  • time：$O(n^2)$ ➔ for loop
  • space：$O(n^2)$ ➔ dp