一、回文與子序列：兩個概念的“折疊”  

回文的核心是對稱：正讀與反讀相同；子序列的核心是順序：原串中從左到右挑選字符，不要求相鄰。LPS 同時擁抱“對稱”與“順序”，于是天然具備兩條性質：  
1. 最優子結構：整個串的最優解可以由更短子串的最優解推出；  
2. 重疊子問題：為了求更長子串，需要反復查詢更短子串的結果。  
這兩條性質，正是動態規劃登場的門票。

二、暴力鏡像：最直觀的“剪-比對”思路  

最容易想到的算法是：生成所有子序列，逐個檢查是否回文，記錄最長。  
- 子序列數量：2^n，指數級；  
- 檢查回文：O(n)。  
總復雜度 O(n * 2^n)，當 n 超過 20 時，計算時間已突破秒級。暴力法像一面哈哈鏡：思路清晰，卻扭曲得無法實用。它提醒我們：必須找到“不必生成所有子序列”的捷徑。

三、折疊法：從“兩端向中心”的第一次降維  

觀察回文特征：首尾字符相等時，它們可以同時進入最優解；首尾字符不等時，最優解必然拋棄其中一端，再對剩余串求解。  
于是得到第一條轉移思路：  
- 若首尾相等，答案 = 2 + 中間子串的最優解；  
- 若首尾不等，答案 = max(去掉首的子串最優解，去掉尾的子串最優解)。  
這條思路把問題規模從 n 降到 n-1 或 n-2，形成“折疊”效應。它像折紙：每次對折，紙張變短，鏡像對稱性保持不變。

四、動態規劃表：二維矩陣的“鏡像坐標系”  

為了存儲“中間子串的最優解”，我們定義二維表 dp[i][j]：原串從位置 i 到 j 的最長回文子序列長度。  
- 行號 i 代表“左端點”，列號 j 代表“右端點”；  
- 對角線 i=j 表示單字符，回文長度為 1；  
- 上三角 i>j 無意義，可忽略或置零。  
填表順序：從“短子串”到“長子串”，即按“子串長度 L”從 2 到 n 逐層計算，確保在計算更長子串時，所依賴的更短子串已就緒。  
這一步像建造一座“鏡像坐標系”：每個格子保存一段“折疊后的對稱長度”，最終 dp[0][n-1] 就是整張紙對折完畢后的答案。

五、轉移方程的“折疊語義”  

填表過程可以口頭描述為：  
“先看兩端字符是否相等，若相等，就把它們折進去，再去看里面那一層；若不等，就分別嘗試去掉左端或右端，選最長的那個。”  
這句口語里藏著轉移方程的全部邏輯，也藏著“為什么時間復雜度是 O(n^2)”的直覺：每一對 (i,j) 只計算一次，且常數時間完成判斷與取值。  
把“口語”翻譯成“心中動畫”，你就擁有了“不依賴紙面公式”的永久記憶。

六、邊界與初始化：對角線的“鏡子起點”  

單字符段 dp[i][i] = 1，這是所有折疊的起始鏡面；  
空段 dp[i][i-1] = 0，代表“折疊到盡頭”時的基準；  
初始化完成，才能讓遞推“有底可托”。邊界像地基：看不見，卻決定整棟樓的平穩。

七、空間優化：從二維到一維的“折疊壓縮”  

觀察填表順序：計算 dp[i][j] 時，只依賴“同一行右側”和“下一行左側”，即 dp[i+1][j] 與 dp[i][j-1]。  
于是可以把“行”壓縮成滾動數組：只用一維表 cur 和 prev，交替更新。  
空間復雜度從 O(n^2) 降到 O(n)，卻仍保持 O(n^2) 時間。  
壓縮像把折紙拍扁：鏡像信息未丟失，只是換了一種“站立方式”。

八、路徑還原：讓“最長”露出真身

dp[i][j] 只給出長度，要得到具體子序列，需要“路徑還原”。  
方法：在填表時同時記錄“選擇方向”——兩端相等則‘折’；不等則記錄‘左’或‘右’。  
最后從兩端向中心回溯，把選擇的字符依次入棧，再翻轉輸出。  
還原像倒放折紙過程：每一步選擇都被記錄，最終展開，得到一面完整的鏡像。

九、變種與擴展：當“折疊”遇見更多約束

1. 最長回文子串（連續）：用中心擴展或 Manacher，O(n)；
2. 最長回文子序列（刪除 k 個）：在 dp 表上加一維“刪除預算”；
3. 最長回文子序列（兩端插入最少字符）：等價于“n - LPS長度”；
4. 兩個字符串的最長公共回文子序列：雙 dp 表，O(n^4) 可優化到 O(n^3)；
5. 帶權回文：每個字符有權重，dp 轉移時累加權重而非計數。  
變種像“折紙藝術”：基礎折法不變，卻在紙張上加入“剪口”“著色”“多層”，衍生出千姿百態。

十、復雜度與性能：O(n^2) 足夠嗎？

- 時間：O(n^2) 對于 n=1000 約為 1e6 次運算，現代 CPU 毫秒級完成；
- 空間：O(n) 滾動數組后，1000 長度僅需 8KB，緩存友好；
- 并行：dp[i][*] 行內無依賴，可按行并行，但常數較小，實用價值有限；
- 近似：若 n>5000，可用“采樣+貪心”得到近似解，誤差 < 5%。  
性能像鏡子：夠用即可，盲目追求 O(n log n) 反而讓代碼難讀、常數變大。

十一、實際應用：為什么面試愛考 LPS？

- DNA 序列比對：尋找回文重復片段；
- 語音信號處理：尋找對稱波形片段；
- 文本編輯器：高亮對稱括號、對稱單詞；
- 驗證碼生成：生成對稱字符串，增加識別難度；
- 數據壓縮：回文片段可用“中心+長度”編碼，減少存儲。  
面試愛考 LPS，是因為它同時考察“動態規劃基礎”“邊界處理”“路徑還原”“復雜度分析”四大維度，又能自然延伸到“回文樹”“Manacher”“插入最少字符”等進階話題。

十二、記憶與直覺：把“折疊”刻進肌肉

把 LPS 的解題過程想象成“折紙游戲”：
1. 展開紙張：原串；
2. 對折兩端：比較首尾；
3. 留下鏡像：相等時折進去；
4. 去掉多余：不等時剪掉短邊；
5. 記錄折痕：dp 表記錄每次選擇；
6. 展開成品：路徑還原得到回文。  
當你能在腦海里播放這段動畫，就不再需要“背誦轉移方程”，而是讓“折紙直覺”指引你寫出代碼、畫出表格、解釋復雜度。

最長回文子序列不是“動態規劃”的終點，而是“折疊思維”的起點。它教會我們：把復雜問題拆成“對稱子問題”，用“表格記錄局部答案”，用“路徑還原整體結構”，最終讓“鏡像”在代碼里浮現。下一次，當你面對“需要對稱”“需要回文”“需要最優”的任何難題，請想起這篇長文，然后在腦海里展開那張紙，對折、再對折，直到最優解在折痕里清晰可見。