---

---

一、引言

在LeetCode的算法題中，子序列相關的問題廣泛存在，例如“最長遞增子序列”、“最長公共子序列”等。這些問題雖然具體題意不同，但本質上都可通過動態(tài)規(guī)劃（Dynamic Programming, DP）來解決。動態(tài)規(guī)劃是一種通過分解子問題并重用子問題解的算法技術，非常適用于這類具有“最優(yōu)子結構”的問題。

本篇文章將以多個典型的LeetCode題目為例，逐步提煉出解決子序列問題的通用方法論，幫助您系統(tǒng)掌握動態(tài)規(guī)劃解決子序列問題的核心技巧。

力扣（LeetCode）題目的鏈接列表：

1. 300. 最長遞增子序列
2. 674. 最長連續(xù)遞增序列
3. 718. 最長重復子數組
4. 1143. 最長公共子序列
5. 53. 最大子序和
6. 392. 判斷子序列
7. 115. 不同的子序列
8. 583. 兩個字符串的刪除操作
9. 72. 編輯距離
10. 647. 回文子串
11. 516. 最長回文子序列

---

二、動態(tài)規(guī)劃方法論深度提煉

動態(tài)規(guī)劃解題方法通常包含以下四個核心步驟：

1. 確定子問題：識別問題的子問題如何劃分，并使得較小問題的解可復用于較大問題的解。
2. 構建最優(yōu)子結構：確保通過每個子問題的最優(yōu)解，組合得到整個問題的最優(yōu)解。
3. 定義狀態(tài)轉移方程：狀態(tài)轉移方程是動態(tài)規(guī)劃的核心，通過它定義出從一個子問題解遞推到另一個子問題解的規(guī)則。
4. 初始化和遞歸順序：設置初始值，明確遞歸或迭代順序。

子序列問題的通用解法模式

在LeetCode的子序列問題中，動態(tài)規(guī)劃的具體實現有以下共通模式：

• dp數組的定義：dp數組一般用來表示問題最優(yōu)解中的特定屬性，例如“最長子序列長度”、“出現次數”、“和”等。dp數組的定義決定了每個子問題的狀態(tài)表示。
• 狀態(tài)轉移方程設計：
  • 對于“最長遞增子序列”類問題，通常通過比較當前元素與前面元素的關系，遞推得到最長子序列的長度。
  • 對于“最長公共子序列”類問題，通常根據兩個字符串的字符是否相等來遞歸或迭代。
  • 對于“編輯距離”類問題，通常需要綜合增刪改三種操作的最小代價。
• 初始化與遞歸順序：大部分問題中，dp數組會有邊界初始值或特定的初始化設定，并采用自底向上或自頂向下的遞歸順序。

---

三、通用方法論應用示例：最長遞增子序列（LeetCode題目300）

題目描述：
題意：給定一個整數數組nums，找到其中最長的嚴格遞增子序列的長度。

示例：

輸入: nums = [10,9,2,5,3,7,101,18]
輸出: 4
解釋: 最長遞增子序列之一是 [2,3,7,101]，因此長度為 4。

---

解題思路：

1. dp數組定義：我們定義dp[i]為以nums[i]結尾的最長遞增子序列的長度。
2. 狀態(tài)轉移方程：對于每一個i，遍歷0到i-1的所有元素j，如果nums[j] < nums[i]，則可以將nums[i]接在以nums[j]結尾的遞增子序列后面，因此有dp[i] = max(dp[i], dp[j] + 1)。
3. 初始化：由于單個元素本身也是一個遞增子序列，因此dp數組的每個元素初始值都設為1。
4. 遞歸順序：從前往后遍歷每個元素，依次計算以每個元素結尾的最長子序列長度。

---

Go 語言代碼實現

func lengthOfLIS(nums []int) int {l := len(nums)result := 1 // 最長遞增子序列的長度，初始化為1dp := make([]int, l) // dp[i]表示以nums[i]結尾的最長遞增子序列長度for i := range dp {dp[i] = 1 // 每個位置的遞增子序列長度至少為1}for i := 1; i < l; i++ {for j := 0; j < i; j++ {if nums[j] < nums[i] { // 只有當nums[i]大于nums[j]時，才能構成遞增子序列dp[i] = max(dp[i], dp[j]+1) // 更新dp[i]為最大長度}}if dp[i] > result {result = dp[i] // 更新全局最長子序列長度}}return result
}// 工具函數：返回兩個整數中的最大值
func max(a, b int) int {if a > b {return a}return b
}

關鍵要點分析：

• 狀態(tài)轉移方程dp[i] = max(dp[i], dp[j] + 1)的設計，體現了子序列問題的核心思想，即將子問題的最優(yōu)解轉移到大問題上。
• 由于每個元素的狀態(tài)僅依賴于之前的元素，因此可以通過嵌套循環(huán)遞推得到最終解。

---

四、最長連續(xù)遞增序列（LeetCode題目674）

題目描述
給定一個未經排序的整數數組nums，找到最長的連續(xù)遞增子序列（子序列是由連續(xù)的數字組成的子數組）的長度。

示例

輸入: nums = [1,3,5,4,7]
輸出: 3
解釋: 最長連續(xù)遞增子序列是 [1,3,5]，長度為3。

---

解題思路：

在該問題中，關鍵在于找到連續(xù)遞增的子序列。我們可以使用動態(tài)規(guī)劃（DP）來實現：

1. dp數組定義：定義dp[i]為以nums[i]結尾的最長連續(xù)遞增子序列的長度。
2. 狀態(tài)轉移方程：如果nums[i] > nums[i-1]，說明當前元素可以與前一個元素構成遞增子序列，因此dp[i] = dp[i-1] + 1。否則，dp[i]重置為1，表示以nums[i]結尾的新起始子序列。
3. 初始化：每個位置的遞增序列至少包含自身一個元素，因此將所有dp[i]初始化為1。
4. 遞歸順序：從左到右遍歷數組，每次更新dp[i]的值。

---

Go 語言代碼實現

func findLengthOfLCIS(nums []int) int {l := len(nums)if l == 0 {return 0}dp := make([]int, l) // dp[i]表示以nums[i]結尾的最長連續(xù)遞增子序列長度for i := range dp {dp[i] = 1 // 初始化為1}result := 1 // 用于存儲最長連續(xù)遞增子序列的長度for i := 1; i < l; i++ {if nums[i] > nums[i-1] { // 如果當前元素大于前一個元素dp[i] = dp[i-1] + 1 // 累加前一個子序列的長度} else {dp[i] = 1 // 否則，重置為1，重新開始}if dp[i] > result {result = dp[i] // 更新全局最長長度}}return result
}

關鍵要點分析：

• 在該題中，連續(xù)遞增的特點使得狀態(tài)轉移方程更為簡單。我們只需判斷當前元素和前一元素的關系，以確定是否延續(xù)或重新開始子序列。
• result變量用于存儲最長的連續(xù)遞增子序列長度，確保在遍歷中隨時得到最終解。

---

五、最長重復子數組（LeetCode題目718）

接下來，我們將介紹最長重復子數組問題，這一題與前面的最長遞增序列問題有所不同，因為它涉及兩個數組的匹配問題。

---

題目描述
給定兩個整數數組nums1和nums2，返回兩個數組中公共的、長度最長的重復子數組的長度。

示例

輸入: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
輸出: 3
解釋: 長度最長的重復子數組是 [3,2,1]，長度為3。

---

解題思路：

1. dp數組定義：我們定義dp[i][j]為在nums1中以第i-1位結尾和在nums2中以第j-1位結尾的最長重復子數組的長度。
2. 狀態(tài)轉移方程：如果nums1[i-1] == nums2[j-1]，則dp[i][j] = dp[i-1][j-1] + 1；否則，dp[i][j] = 0。
3. 初始化：dp[i][0]和dp[0][j]初始化為0，因為任一數組為空時沒有公共子數組。
4. 遞歸順序：從左到右、從上到下填充二維dp數組，并在過程中記錄最長的子數組長度。

---

Go 語言代碼實現

func findLength(nums1 []int, nums2 []int) int {l1, l2 := len(nums1), len(nums2)dp := make([][]int, l1+1) // dp[i][j]表示以nums1[i-1]和nums2[j-1]結尾的最長重復子數組長度for i := range dp {dp[i] = make([]int, l2+1)}result := 0 // 用于記錄最長重復子數組的長度for i := 1; i <= l1; i++ {for j := 1; j <= l2; j++ {if nums1[i-1] == nums2[j-1] { // 如果兩數組對應位置的元素相等dp[i][j] = dp[i-1][j-1] + 1 // 延長前一個子數組的長度if dp[i][j] > result {result = dp[i][j] // 更新全局最長長度}} else {dp[i][j] = 0 // 否則沒有公共子數組，重置為0}}}return result
}

關鍵要點分析：

• 該題的dp數組使用二維結構，以便對比nums1和nums2的每個位置組合。
• 每次找到一個相同元素時，延長重復子數組的長度；否則，將當前子問題解置零。
• 通過對dp數組的累積更新，記錄并獲取最長的公共子數組長度。

---

好的，接下來是最長公共子序列問題（LeetCode題目1143）的詳細解析。

---

六、最長公共子序列（LeetCode題目1143）

題目描述
給定兩個字符串text1和text2，返回這兩個字符串的最長公共子序列的長度。如果不存在公共子序列，則返回0。子序列不要求在原字符串中是連續(xù)的，但順序必須一致。

示例

輸入: text1 = "abcde", text2 = "ace" 
輸出: 3  
解釋: 最長公共子序列是 "ace"，因此返回3。

---

解題思路：

最長公共子序列問題與前面的最長重復子數組不同，它關注的是子序列（不連續(xù)）的匹配，而不是子數組（連續(xù)）的匹配。該問題可使用動態(tài)規(guī)劃解決，步驟如下：

1. dp數組定義：定義dp[i][j]為字符串text1前i個字符和字符串text2前j個字符的最長公共子序列的長度。
2. 狀態(tài)轉移方程：如果text1[i-1] == text2[j-1]，則dp[i][j] = dp[i-1][j-1] + 1；否則，dp[i][j] = max(dp[i-1][j], dp[i][j-1])。這個方程表示如果當前字符匹配，則可以在前一個狀態(tài)基礎上延長子序列；如果不匹配，則取兩個可能情況的最大值。
3. 初始化：如果任一字符串為空（即dp[i][0]或dp[0][j]），則公共子序列長度為0。
4. 遞歸順序：按行或按列填充二維dp數組。

---

Go 語言代碼實現

func longestCommonSubsequence(text1, text2 string) int {l1, l2 := len(text1), len(text2)dp := make([][]int, l1+1) // dp[i][j]表示text1前i個字符和text2前j個字符的最長公共子序列長度for i := range dp {dp[i] = make([]int, l2+1)}for i := 1; i <= l1; i++ {for j := 1; j <= l2; j++ {if text1[i-1] == text2[j-1] { // 當兩個字符相等時dp[i][j] = dp[i-1][j-1] + 1 // 延長公共子序列長度} else {dp[i][j] = max(dp[i-1][j], dp[i][j-1]) // 否則取相鄰位置的最大長度}}}return dp[l1][l2] // 返回最長公共子序列的長度
}// 工具函數：返回兩個整數中的最大值
func max(a, b int) int {if a > b {return a}return b
}

關鍵要點分析：

• 狀態(tài)轉移方程的設計清晰表達了最長公共子序列的遞歸關系：當兩個字符匹配時，可通過延長已有公共子序列長度獲得新解。
• dp[i][j]的計算依賴于其左、上和左上方位置的值，因此填充順序需從左到右、從上到下。
• 通過遍歷dp數組的終點值，即dp[l1][l2]，得到最長公共子序列的長度。

---

七、最大子序和（LeetCode題目53）

接下來，我們介紹最大子序和問題，這是一個經典的動態(tài)規(guī)劃問題，要求在一個數組中找到連續(xù)子數組的最大和。

---

題目描述
給定一個整數數組nums，找到具有最大和的連續(xù)子數組，并返回其和。

示例

輸入: nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出: 6
解釋: 連續(xù)子數組 [4,-1,2,1] 的和最大，為 6。

---

解題思路：

該題目要求尋找最大子序和，屬于“區(qū)間最大和”問題?？梢酝ㄟ^動態(tài)規(guī)劃來解決：

1. dp數組定義：定義dp[i]為以nums[i]結尾的最大子序和。
2. 狀態(tài)轉移方程：若前一個位置的dp[i-1]值大于0，則將其加入當前元素形成新子數組；否則，當前元素單獨作為新子序列的起點。因此，dp[i] = max(dp[i-1] + nums[i], nums[i])。
3. 初始化：dp[0] = nums[0]，因為以第一個元素結尾的最大子序和即為nums[0]。
4. 遞歸順序：從左到右遍歷數組，逐步累積計算最大和。

---

Go 語言代碼實現

func maxSubArray(nums []int) int {l := len(nums)dp := make([]int, l) // dp[i]表示以nums[i]結尾的最大子序和dp[0] = nums[0]result := nums[0] // 存儲全局最大和for i := 1; i < l; i++ {dp[i] = max(dp[i-1]+nums[i], nums[i]) // 更新dp[i]為當前最大和if dp[i] > result {result = dp[i] // 更新全局最大和}}return result
}

關鍵要點分析：

• 該題的dp數組設計特別之處在于，它在每一步選擇是否將前面的子序列結果帶入當前狀態(tài)。
• 狀態(tài)轉移方程中的max(dp[i-1] + nums[i], nums[i])確保了我們每一步都可以選擇“重開”子序列或“延續(xù)”已有的子序列，從而實現最優(yōu)子結構。

---

八、判斷子序列（LeetCode題目392）

最后，我們來看一個簡單但巧妙的子序列問題，即如何判斷一個字符串是否是另一個字符串的子序列。

---

題目描述
給定字符串s和t，判斷s是否是t的子序列。可以假設兩個字符串均僅包含英文小寫字母。

示例

輸入: s = "abc", t = "ahbgdc"
輸出: true
解釋: s 是 t 的子序列。

---

解題思路：

這個問題不需要完整的動態(tài)規(guī)劃來解決，因為子序列要求順序一致但不連續(xù)。我們可以通過雙指針或DP判斷每個字符的匹配情況。

1. dp數組定義：使用雙指針分別遍歷s和t，若s[i] == t[j]，則移動s的指針，否則僅移動t的指針。
2. 狀態(tài)轉移方程：無經典的DP狀態(tài)轉移方程，本題可用指針遍歷簡化實現。
3. 初始化：雙指針從字符串起始位置開始。
4. 遞歸順序：順序遍歷s和t。

---

Go 語言代碼實現

//動態(tài)規(guī)劃

func isSubsequence1(s, t string) bool {ls, lt := len(s), len(t)dp := make([][]int, ls+1)var maxLength intfor i := range dp {dp[i] = make([]int, lt+1)}for i := 1; i <= ls; i++ {for j := 1; j <= lt; j++ {if s[i-1] == t[j-1] {dp[i][j] = dp[i-1][j-1] + 1} else {dp[i][j] = dp[i][j-1]}if maxLength < dp[i][j] {maxLength = dp[i][j]}}}return maxLength == ls
}

//雙指針

func isSubsequence(s, t string) bool {i, j := 0, 0ls, lt := len(s), len(t)for i < ls && j < lt {if s[i] == t[j] { // 若字符匹配，移動s的指針i++}j++ // 始終移動t的指針}return i == ls // 若s的指針移動到末尾，則s是t的子序列
}

關鍵要點分析：

• 雙指針法在保證正確性的前提下，以最優(yōu)復雜度O(n)解決了子序列判定問題。
• 相較于完整的DP表結構，雙指針方法簡潔且高效，非常適合子序列匹配類問題。

---

好的，接下來我們繼續(xù)介紹 不同的子序列（LeetCode題目115）的問題及其解法。

---

九、不同的子序列（LeetCode題目115）

題目描述
給定一個字符串s和一個字符串t，計算在s的子序列中t出現的個數。

示例

輸入: s = "rabbbit", t = "rabbit"
輸出: 3
解釋: 如下圖所示，有 3 種可以從 s 中得到 "rabbit" 的方式。

---

解題思路：

在該題中，我們需要統(tǒng)計t在s中作為子序列出現的次數。可以使用動態(tài)規(guī)劃，通過分析字符是否匹配，遞推出每個子問題的解。具體步驟如下：

1. dp數組定義：定義dp[i][j]為s的前i個字符中t的前j個字符出現的次數。
2. 狀態(tài)轉移方程：
   • 當s[i-1] == t[j-1]時，dp[i][j] = dp[i-1][j-1] + dp[i-1][j]，表示當前字符相等時，子序列可以選擇匹配當前字符或忽略當前字符；
   • 當s[i-1] != t[j-1]時，dp[i][j] = dp[i-1][j]，表示字符不匹配的情況下，只能通過忽略當前字符來求解。
3. 初始化：dp[i][0] = 1，即t為空時，是任何字符串的子序列，子序列出現次數為1。
4. 遞歸順序：按行遍歷dp表，以自頂向下、自左向右的順序填充。

---

Go 語言代碼實現

func numDistinct(s string, t string) int {ls, lt := len(s), len(t)dp := make([][]int, ls+1) // dp[i][j]表示s的前i個字符中包含t的前j個字符的子序列個數for i := range dp {dp[i] = make([]int, lt+1)dp[i][0] = 1 // 當t為空字符串時，是s的子序列}for i := 1; i <= ls; i++ {for j := 1; j <= lt; j++ {if s[i-1] == t[j-1] {dp[i][j] = dp[i-1][j-1] + dp[i-1][j] // 匹配或不匹配當前字符} else {dp[i][j] = dp[i-1][j] // 不匹配時，忽略s的當前字符}}}return dp[ls][lt]
}

關鍵要點分析：

• 該題的動態(tài)規(guī)劃表格通過字符匹配與否，確保了子序列匹配的所有可能組合都被考慮。
• 通過逐層累積每一子問題的最優(yōu)解，dp[ls][lt]即為s中出現t的所有方式。

---

十、兩個字符串的刪除操作（LeetCode題目583）

接下來，我們將探討兩個字符串的刪除操作這一問題，該題的本質是在兩個字符串之間尋找相似部分，從而最小化刪除次數。

---

題目描述
給定兩個單詞word1和word2，返回使得兩個單詞相同所需的最小步數。每步可以刪除任意一個字符串中的一個字符。

示例

輸入: word1 = "sea", word2 = "eat"
輸出: 2
解釋: 將 "sea" 變?yōu)?"ea" 并刪除 "t"，最少需要 2 步。

---

解題思路：

該題的核心在于最小化兩個字符串的刪除操作，具體實現可以通過找到最長公共子序列來進行。步驟如下：

1. dp數組定義：定義dp[i][j]為將word1的前i個字符與word2的前j個字符變?yōu)橄嗤璧淖钚〔綌怠?/li>
2. 狀態(tài)轉移方程：
   • 當word1[i-1] == word2[j-1]時，字符相等，不需刪除操作，故dp[i][j] = dp[i-1][j-1]；
   • 當word1[i-1] != word2[j-1]時，考慮刪除一個字符后使得剩余字符匹配的最小代價，故dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1。
3. 初始化：dp[i][0] = i，表示word2為空時，需要刪除word1的所有字符；同理，dp[0][j] = j。
4. 遞歸順序：從左到右逐步構建二維dp表。

---

Go 語言代碼實現

func minDistance(word1 string, word2 string) int {l1, l2 := len(word1), len(word2)dp := make([][]int, l1+1) // dp[i][j]表示將word1的前i個字符與word2的前j個字符變?yōu)橄嗤璧淖钚〔綌?/span>for i := range dp {dp[i] = make([]int, l2+1)dp[i][0] = i // 初始化第一列}for j := range dp[0] {dp[0][j] = j // 初始化第一行}for i := 1; i <= l1; i++ {for j := 1; j <= l2; j++ {if word1[i-1] == word2[j-1] {dp[i][j] = dp[i-1][j-1] // 如果字符相等，不需要額外操作} else {dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1 // 選擇刪除的最小代價}}}return dp[l1][l2]
}// 工具函數：返回兩個整數中的較小值
func min(a, b int) int {if a < b {return a}return b
}

關鍵要點分析：

• 該問題可以看作是“編輯距離”的簡化版，主要涉及刪除操作，因此只需考慮刪除的最小代價。
• dp[i][j]記錄了當前最小步數，并通過累積前面的最小操作實現了從局部最優(yōu)解推向全局最優(yōu)解。

---

十一、編輯距離（LeetCode題目72）

編輯距離是經典的動態(tài)規(guī)劃問題之一，主要關注插入、刪除和替換操作的最小代價。

---

題目描述
給定兩個單詞word1和word2，計算將word1轉換成word2所需的最小操作數?？梢詫σ粋€單詞執(zhí)行插入、刪除或替換操作。

示例

輸入: word1 = "horse", word2 = "ros"
輸出: 3
解釋: horse -> rorse (替換 'h' 為 'r') -> rose (刪除 'r') -> ros (刪除 'e')

---

解題思路：

該問題可通過動態(tài)規(guī)劃解決，逐步最小化每次編輯的代價：

1. dp數組定義：dp[i][j]為將word1的前i個字符變?yōu)?code>word2的前j個字符所需的最小編輯次數。
2. 狀態(tài)轉移方程：
   • 如果word1[i-1] == word2[j-1]，則無需編輯，dp[i][j] = dp[i-1][j-1]；
   • 若不相等，則取插入、刪除、替換操作的最小代價，dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1。
3. 初始化：當word2為空時，dp[i][0] = i；同理，dp[0][j] = j。
4. 遞歸順序：逐步填充整個dp表，從左到右、從上到下。

---

Go 語言代碼實現

func minDistance(word1, word2 string) int {l1, l2 := len(word1), len(word2)dp := make([][]int, l1+1) // dp[i][j]表示將word1的前i個字符變?yōu)閣ord2的前j個字符的最小編輯次數for i := range dp {dp[i] = make([]int, l2+1)dp[i][0] = i // 初始化第一列}for j := range dp[0] {dp[0][j] = j // 初始化第一行}for i := 1; i <= l1; i++ {for j := 1; j <= l2; j++ {if word1[i-1] == word2[j-1] {dp[i][j] = dp[i-1][j-1] // 如果字符相等，不需額外操作} else {dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 // 插入、刪除、替換的最小代價}}}return dp[l1][l2]
}// 工具函數：返回三個整數中的最小值
func min(a, b, c int) int {if a < b {if a < c {return a}return c}if b < c {return b}return c
}

關鍵要點分析：

• 本題動態(tài)規(guī)劃的核心在于清晰的狀態(tài)轉移方程，將字符是否匹配的三種編輯操作的最小代價逐步遞推。
• dp[i][j]通過三種操作的最小代價累積，得出將word1轉換成word2所需的最小編輯距離。

---

好的，接下來我們繼續(xù)介紹 回文子串（LeetCode題目647）的問題及其解法。

---

十二、回文子串（LeetCode題目647）

題目描述
給定一個字符串s，計算并返回s中的回文子串數量。具有相同順序且相同字符的子串稱為回文。

示例

輸入: s = "abc"
輸出: 3
解釋: 回文子串為 ["a","b","c"]。

輸入: s = "aaa"
輸出: 6
解釋: 回文子串為 ["a","a","a","aa","aa","aaa"]。

---

解題思路：

這道題要求我們統(tǒng)計字符串中的回文子串數量，可以利用動態(tài)規(guī)劃來判斷每個子串是否為回文，并記錄回文的數量。

1. dp數組定義：定義dp[i][j]表示從字符s[i]到s[j]的子串是否是回文子串。若為回文子串，則dp[i][j] = true，否則為false。
2. 狀態(tài)轉移方程：
   • 當s[i] == s[j]且j - i <= 1時，dp[i][j] = true；
   • 否則，當s[i] == s[j]且dp[i+1][j-1] = true時，dp[i][j] = true。
3. 初始化：長度為1的子串均為回文，因此對每個位置i，dp[i][i] = true。
4. 遞歸順序：從右下角向左上角遍歷dp數組，逐步填充。

---

Go 語言代碼實現

func countSubstrings(s string) int {l := len(s)dp := make([][]bool, l) // dp[i][j]表示s從i到j的子串是否為回文for i := range dp {dp[i] = make([]bool, l)}result := 0 // 用于記錄回文子串的數量for i := l - 1; i >= 0; i-- { // 從右下角到左上角填充dp數組for j := i; j < l; j++ {if s[i] == s[j] && (j-i <= 1 || dp[i+1][j-1]) {dp[i][j] = true // s[i:j+1]為回文result++ // 每找到一個回文子串就計數加一}}}return result
}

關鍵要點分析：

• 狀態(tài)轉移方程dp[i][j]結合字符相等性和內部子串的回文性有效判斷了每個子串的回文性質。
• 遍歷順序為從右下角到左上角，保證每個較短子串的狀態(tài)在較長子串狀態(tài)確定前已完成更新。

---

十三、最長回文子序列（LeetCode題目516）

最后，我們來看一道回文序列問題，要求在一個字符串中找到最長的回文子序列長度。

---

題目描述
給定一個字符串s，找到其中最長的回文子序列的長度。子序列不要求是連續(xù)的，但順序必須保持一致。

示例

輸入: s = "bbbab"
輸出: 4
解釋: "bbbb" 是最長的回文子序列。

---

解題思路：

該問題可以使用動態(tài)規(guī)劃通過遞歸判斷字符的對稱性來解決。

1. dp數組定義：定義dp[i][j]為字符串s從位置i到j的子串的最長回文子序列長度。
2. 狀態(tài)轉移方程：
   • 若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])。
3. 初始化：對于每個位置i，dp[i][i] = 1，即單個字符的回文長度為1。
4. 遞歸順序：從下到上、從左到右填充dp數組，保證子問題優(yōu)先求解。

---

Go 語言代碼實現

func longestPalindromeSubseq(s string) int {l := len(s)dp := make([][]int, l) // dp[i][j]表示s從i到j的最長回文子序列長度for i := range dp {dp[i] = make([]int, l)dp[i][i] = 1 // 初始化單個字符的回文長度為1}for i := l - 1; i >= 0; i-- { // 從下到上遍歷for j := i + 1; j < l; j++ { // 從左到右填充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]) // 否則取左右子問題的最大值}}}return dp[0][l-1] // 返回整個字符串的最長回文子序列長度
}// 工具函數：返回兩個整數中的最大值
func max(a, b int) int {if a > b {return a}return b
}

關鍵要點分析：

• 本題通過遞歸狀態(tài)方程有效地判斷了字符對稱性，dp[i][j]記錄每個子問題的最優(yōu)解，保證子問題遞推到全局。
• 本題與最長回文子串問題不同，最長回文子序列并不要求子序列連續(xù)，狀態(tài)轉移時依賴左、下和左下角元素。

---

十四、結論

在本篇文章中，我們系統(tǒng)地梳理了LeetCode中一系列子序列類問題的動態(tài)規(guī)劃解法。通過dp數組定義、狀態(tài)轉移方程設計、初始化、遞歸順序等方面，我們展示了如何構建并解決常見的子序列問題。動態(tài)規(guī)劃不僅要求細致的代碼實現，更強調對問題的整體分解與子問題的遞推組合，這些方法論將有助于提升算法的解決能力。希望本文對您深入理解和掌握動態(tài)規(guī)劃有所幫助！