解題說明
Longest Palindromic Subsequence
題目描述：
給定一個字串 s，找出其最長回文子序列（Palindromic Subsequence）的長度。子序列不要求連續。
解題思路：
使用區間 DP。定義 dp[i][j] 為子字串 s[i..j] 中最長回文子序列的長度。
轉移規則：
- 若
s[i] == s[j]：dp[i][j] = dp[i+1][j-1] + 2（兩端字元可加入回文） - 若
s[i] != s[j]：dp[i][j] = max(dp[i+1][j], dp[i][j-1])（嘗試去掉左端或右端）
基礎情況：dp[i][i] = 1（單個字元是長度 1 的回文）。
遍歷順序：從短區間到長區間（i 從大到小，j 從小到大），確保計算 dp[i][j] 時所需的子問題已解決。
最終答案為 dp[0][n-1]。
C++ 解法
複雜度分析
時間複雜度：O(n²) — 填充 n x n 的 DP 表，每格 O(1) 計算。
空間複雜度：O(n²) — 二維 DP 表大小。可優化至 O(n) 使用滾動陣列。
虛擬碼
1. Initialize dp[n][n] with all zeros
2. For each i: dp[i][i] = 1
3. For length from 2 to n:
For i from 0 to n - length:
j = i + length - 1
If s[i] == s[j]: dp[i][j] = dp[i+1][j-1] + 2
Else: dp[i][j] = max(dp[i+1][j], dp[i][j-1])
4. Return dp[0][n-1]其他解法
LCS 轉換法：最長回文子序列等於原字串 s 與其反轉 s' 的最長公共子序列（LCS）。因為 LCS 找出的公共部分在原串中正讀和反讀都一樣，即回文。時間 O(n²)，空間 O(n²)（可優化至 O(n)）。概念上將問題歸約為已知問題。
空間優化至 O(n)：觀察到 dp[i][j] 只依賴 dp[i+1][j-1]、dp[i+1][j]、dp[i][j-1]，可用一維陣列 + 一個暫存變數完成。適合面試中展示優化能力。
延伸思考
- 最長回文子序列與最長回文子字串（LeetCode 5）有什麼本質區別？為什麼子字串問題也能用 DP 解但轉移不同？
- 若要求印出最長回文子序列本身（而非僅長度），如何回溯 DP 表？
- 將字串 s 變成回文需要的最少插入次數是多少？與此題的關係是什麼？（LeetCode 1312）