wordpress小說網(wǎng)站模板下載網(wǎng)站按天扣費優(yōu)化推廣
文章目錄
- 一、引言
- 二、動態(tài)規(guī)劃方法論深度提煉
- 子序列問題的通用解法模式
- 三、通用方法論應用示例：最長遞增子序列（LeetCode題目300）
- Go 語言代碼實現(xiàn)
- 四、最長連續(xù)遞增序列（LeetCode題目674）
- Go 語言代碼實現(xiàn)
- 五、最長重復子數(shù)組（LeetCode題目718）
- Go 語言代碼實現(xiàn)
- 六、最長公共子序列（LeetCode題目1143）
- Go 語言代碼實現(xiàn)
- 七、最大子序和（LeetCode題目53）
- Go 語言代碼實現(xiàn)
- 八、判斷子序列（LeetCode題目392）
- Go 語言代碼實現(xiàn)
- 九、不同的子序列（LeetCode題目115）
- Go 語言代碼實現(xiàn)
- 十、兩個字符串的刪除操作（LeetCode題目583）
- Go 語言代碼實現(xiàn)
- 十一、編輯距離（LeetCode題目72）
- Go 語言代碼實現(xiàn)
- 十二、回文子串（LeetCode題目647）
- Go 語言代碼實現(xiàn)
- 十三、最長回文子序列（LeetCode題目516）
- Go 語言代碼實現(xiàn)
- 十四、結(jié)論
一、引言
在LeetCode的算法題中，子序列相關(guān)的問題廣泛存在，例如“最長遞增子序列”、“最長公共子序列”等。這些問題雖然具體題意不同，但本質(zhì)上都可通過動態(tài)規(guī)劃（Dynamic Programming, DP）來解決。動態(tài)規(guī)劃是一種通過分解子問題并重用子問題解的算法技術(shù)，非常適用于這類具有“最優(yōu)子結(jié)構(gòu)”的問題。
本篇文章將以多個典型的LeetCode題目為例，逐步提煉出解決子序列問題的通用方法論，幫助您系統(tǒng)掌握動態(tài)規(guī)劃解決子序列問題的核心技巧。
力扣（LeetCode）題目的鏈接列表：
- 300. 最長遞增子序列
- 674. 最長連續(xù)遞增序列
- 718. 最長重復子數(shù)組
- 1143. 最長公共子序列
- 53. 最大子序和
- 392. 判斷子序列
- 115. 不同的子序列
- 583. 兩個字符串的刪除操作
- 72. 編輯距離
- 647. 回文子串
- 516. 最長回文子序列
二、動態(tài)規(guī)劃方法論深度提煉
動態(tài)規(guī)劃解題方法通常包含以下四個核心步驟：
- 確定子問題：識別問題的子問題如何劃分，并使得較小問題的解可復用于較大問題的解。
- 構(gòu)建最優(yōu)子結(jié)構(gòu)：確保通過每個子問題的最優(yōu)解，組合得到整個問題的最優(yōu)解。
- 定義狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程是動態(tài)規(guī)劃的核心，通過它定義出從一個子問題解遞推到另一個子問題解的規(guī)則。
- 初始化和遞歸順序：設(shè)置初始值，明確遞歸或迭代順序。
子序列問題的通用解法模式
在LeetCode的子序列問題中，動態(tài)規(guī)劃的具體實現(xiàn)有以下共通模式：
- dp數(shù)組的定義：
dp數(shù)組一般用來表示問題最優(yōu)解中的特定屬性，例如“最長子序列長度”、“出現(xiàn)次數(shù)”、“和”等。dp數(shù)組的定義決定了每個子問題的狀態(tài)表示。 - 狀態(tài)轉(zhuǎn)移方程設(shè)計：
- 對于“最長遞增子序列”類問題，通常通過比較當前元素與前面元素的關(guān)系，遞推得到最長子序列的長度。
- 對于“最長公共子序列”類問題，通常根據(jù)兩個字符串的字符是否相等來遞歸或迭代。
- 對于“編輯距離”類問題，通常需要綜合增刪改三種操作的最小代價。
- 初始化與遞歸順序：大部分問題中，dp數(shù)組會有邊界初始值或特定的初始化設(shè)定，并采用自底向上或自頂向下的遞歸順序。
三、通用方法論應用示例：最長遞增子序列（LeetCode題目300）
題目描述：
題意：給定一個整數(shù)數(shù)組nums，找到其中最長的嚴格遞增子序列的長度。
示例：
輸入: nums = [10,9,2,5,3,7,101,18]
輸出: 4
解釋: 最長遞增子序列之一是 [2,3,7,101]，因此長度為 4。
解題思路：
- dp數(shù)組定義：我們定義
dp[i]為以nums[i]結(jié)尾的最長遞增子序列的長度。 - 狀態(tài)轉(zhuǎn)移方程：對于每一個
i，遍歷0到i-1的所有元素j，如果nums[j] < nums[i]，則可以將nums[i]接在以nums[j]結(jié)尾的遞增子序列后面，因此有dp[i] = max(dp[i], dp[j] + 1)。 - 初始化：由于單個元素本身也是一個遞增子序列，因此
dp數(shù)組的每個元素初始值都設(shè)為1。 - 遞歸順序：從前往后遍歷每個元素，依次計算以每個元素結(jié)尾的最長子序列長度。
Go 語言代碼實現(xiàn)
func lengthOfLIS(nums []int) int {l := len(nums)result := 1 // 最長遞增子序列的長度，初始化為1dp := make([]int, l) // dp[i]表示以nums[i]結(jié)尾的最長遞增子序列長度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]時，才能構(gòu)成遞增子序列dp[i] = max(dp[i], dp[j]+1) // 更新dp[i]為最大長度}}if dp[i] > result {result = dp[i] // 更新全局最長子序列長度}}return result
}// 工具函數(shù)：返回兩個整數(shù)中的最大值
func max(a, b int) int {if a > b {return a}return b
}
關(guān)鍵要點分析：
- 狀態(tài)轉(zhuǎn)移方程
dp[i] = max(dp[i], dp[j] + 1)的設(shè)計，體現(xiàn)了子序列問題的核心思想，即將子問題的最優(yōu)解轉(zhuǎn)移到大問題上。 - 由于每個元素的狀態(tài)僅依賴于之前的元素，因此可以通過嵌套循環(huán)遞推得到最終解。
四、最長連續(xù)遞增序列（LeetCode題目674）
題目描述
給定一個未經(jīng)排序的整數(shù)數(shù)組nums，找到最長的連續(xù)遞增子序列（子序列是由連續(xù)的數(shù)字組成的子數(shù)組）的長度。
示例
輸入: nums = [1,3,5,4,7]
輸出: 3
解釋: 最長連續(xù)遞增子序列是 [1,3,5]，長度為3。
解題思路：
在該問題中，關(guān)鍵在于找到連續(xù)遞增的子序列。我們可以使用動態(tài)規(guī)劃（DP）來實現(xiàn)：
- dp數(shù)組定義：定義
dp[i]為以nums[i]結(jié)尾的最長連續(xù)遞增子序列的長度。 - 狀態(tài)轉(zhuǎn)移方程：如果
nums[i] > nums[i-1]，說明當前元素可以與前一個元素構(gòu)成遞增子序列，因此dp[i] = dp[i-1] + 1。否則，dp[i]重置為1，表示以nums[i]結(jié)尾的新起始子序列。 - 初始化：每個位置的遞增序列至少包含自身一個元素，因此將所有
dp[i]初始化為1。 - 遞歸順序：從左到右遍歷數(shù)組，每次更新
dp[i]的值。
Go 語言代碼實現(xiàn)
func findLengthOfLCIS(nums []int) int {l := len(nums)if l == 0 {return 0}dp := make([]int, l) // dp[i]表示以nums[i]結(jié)尾的最長連續(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
}
關(guān)鍵要點分析：
- 在該題中，連續(xù)遞增的特點使得狀態(tài)轉(zhuǎn)移方程更為簡單。我們只需判斷當前元素和前一元素的關(guān)系，以確定是否延續(xù)或重新開始子序列。
result變量用于存儲最長的連續(xù)遞增子序列長度，確保在遍歷中隨時得到最終解。
五、最長重復子數(shù)組（LeetCode題目718）
接下來，我們將介紹最長重復子數(shù)組問題，這一題與前面的最長遞增序列問題有所不同，因為它涉及兩個數(shù)組的匹配問題。
題目描述
給定兩個整數(shù)數(shù)組nums1和nums2，返回兩個數(shù)組中公共的、長度最長的重復子數(shù)組的長度。
示例
輸入: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
輸出: 3
解釋: 長度最長的重復子數(shù)組是 [3,2,1]，長度為3。
解題思路：
- dp數(shù)組定義：我們定義
dp[i][j]為在nums1中以第i-1位結(jié)尾和在nums2中以第j-1位結(jié)尾的最長重復子數(shù)組的長度。 - 狀態(tài)轉(zhuǎn)移方程：如果
nums1[i-1] == nums2[j-1]，則dp[i][j] = dp[i-1][j-1] + 1；否則，dp[i][j] = 0。 - 初始化：
dp[i][0]和dp[0][j]初始化為0，因為任一數(shù)組為空時沒有公共子數(shù)組。 - 遞歸順序：從左到右、從上到下填充二維
dp數(shù)組，并在過程中記錄最長的子數(shù)組長度。
Go 語言代碼實現(xiàn)
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]結(jié)尾的最長重復子數(shù)組長度for i := range dp {dp[i] = make([]int, l2+1)}result := 0 // 用于記錄最長重復子數(shù)組的長度for i := 1; i <= l1; i++ {for j := 1; j <= l2; j++ {if nums1[i-1] == nums2[j-1] { // 如果兩數(shù)組對應位置的元素相等dp[i][j] = dp[i-1][j-1] + 1 // 延長前一個子數(shù)組的長度if dp[i][j] > result {result = dp[i][j] // 更新全局最長長度}} else {dp[i][j] = 0 // 否則沒有公共子數(shù)組，重置為0}}}return result
}
關(guān)鍵要點分析：
- 該題的
dp數(shù)組使用二維結(jié)構(gòu)，以便對比nums1和nums2的每個位置組合。 - 每次找到一個相同元素時，延長重復子數(shù)組的長度；否則，將當前子問題解置零。
- 通過對
dp數(shù)組的累積更新，記錄并獲取最長的公共子數(shù)組長度。
好的，接下來是最長公共子序列問題（LeetCode題目1143）的詳細解析。
六、最長公共子序列（LeetCode題目1143）
題目描述
給定兩個字符串text1和text2，返回這兩個字符串的最長公共子序列的長度。如果不存在公共子序列，則返回0。子序列不要求在原字符串中是連續(xù)的，但順序必須一致。
示例
輸入: text1 = "abcde", text2 = "ace"
輸出: 3
解釋: 最長公共子序列是 "ace"，因此返回3。
解題思路：
最長公共子序列問題與前面的最長重復子數(shù)組不同，它關(guān)注的是子序列（不連續(xù)）的匹配，而不是子數(shù)組（連續(xù)）的匹配。該問題可使用動態(tài)規(guī)劃解決，步驟如下：
- dp數(shù)組定義：定義
dp[i][j]為字符串text1前i個字符和字符串text2前j個字符的最長公共子序列的長度。 - 狀態(tài)轉(zhuǎn)移方程：如果
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)基礎(chǔ)上延長子序列；如果不匹配，則取兩個可能情況的最大值。 - 初始化：如果任一字符串為空（即
dp[i][0]或dp[0][j]），則公共子序列長度為0。 - 遞歸順序：按行或按列填充二維
dp數(shù)組。
Go 語言代碼實現(xiàn)
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] // 返回最長公共子序列的長度
}// 工具函數(shù)：返回兩個整數(shù)中的最大值
func max(a, b int) int {if a > b {return a}return b
}
關(guān)鍵要點分析：
- 狀態(tài)轉(zhuǎn)移方程的設(shè)計清晰表達了最長公共子序列的遞歸關(guān)系：當兩個字符匹配時，可通過延長已有公共子序列長度獲得新解。
dp[i][j]的計算依賴于其左、上和左上方位置的值，因此填充順序需從左到右、從上到下。- 通過遍歷
dp數(shù)組的終點值，即dp[l1][l2]，得到最長公共子序列的長度。
七、最大子序和（LeetCode題目53）
接下來，我們介紹最大子序和問題，這是一個經(jīng)典的動態(tài)規(guī)劃問題，要求在一個數(shù)組中找到連續(xù)子數(shù)組的最大和。
題目描述
給定一個整數(shù)數(shù)組nums，找到具有最大和的連續(xù)子數(shù)組，并返回其和。
示例
輸入: nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6。
解題思路：
該題目要求尋找最大子序和，屬于“區(qū)間最大和”問題?？梢酝ㄟ^動態(tài)規(guī)劃來解決：
- dp數(shù)組定義：定義
dp[i]為以nums[i]結(jié)尾的最大子序和。 - 狀態(tài)轉(zhuǎn)移方程：若前一個位置的
dp[i-1]值大于0，則將其加入當前元素形成新子數(shù)組；否則，當前元素單獨作為新子序列的起點。因此，dp[i] = max(dp[i-1] + nums[i], nums[i])。 - 初始化：
dp[0] = nums[0]，因為以第一個元素結(jié)尾的最大子序和即為nums[0]。 - 遞歸順序：從左到右遍歷數(shù)組，逐步累積計算最大和。
Go 語言代碼實現(xiàn)
func maxSubArray(nums []int) int {l := len(nums)dp := make([]int, l) // dp[i]表示以nums[i]結(jié)尾的最大子序和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
}
關(guān)鍵要點分析：
- 該題的
dp數(shù)組設(shè)計特別之處在于，它在每一步選擇是否將前面的子序列結(jié)果帶入當前狀態(tài)。 - 狀態(tài)轉(zhuǎn)移方程中的
max(dp[i-1] + nums[i], nums[i])確保了我們每一步都可以選擇“重開”子序列或“延續(xù)”已有的子序列，從而實現(xiàn)最優(yōu)子結(jié)構(gòu)。
八、判斷子序列（LeetCode題目392）
最后，我們來看一個簡單但巧妙的子序列問題，即如何判斷一個字符串是否是另一個字符串的子序列。
題目描述
給定字符串s和t，判斷s是否是t的子序列?？梢约僭O(shè)兩個字符串均僅包含英文小寫字母。
示例
輸入: s = "abc", t = "ahbgdc"
輸出: true
解釋: s 是 t 的子序列。
解題思路：
這個問題不需要完整的動態(tài)規(guī)劃來解決，因為子序列要求順序一致但不連續(xù)。我們可以通過雙指針或DP判斷每個字符的匹配情況。
- dp數(shù)組定義：使用雙指針分別遍歷
s和t，若s[i] == t[j]，則移動s的指針，否則僅移動t的指針。 - 狀態(tài)轉(zhuǎn)移方程：無經(jīng)典的DP狀態(tài)轉(zhuǎn)移方程，本題可用指針遍歷簡化實現(xiàn)。
- 初始化：雙指針從字符串起始位置開始。
- 遞歸順序：順序遍歷
s和t。
Go 語言代碼實現(xiàn)
//動態(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的子序列
}
關(guān)鍵要點分析：
- 雙指針法在保證正確性的前提下，以最優(yōu)復雜度
O(n)解決了子序列判定問題。 - 相較于完整的DP表結(jié)構(gòu)，雙指針方法簡潔且高效，非常適合子序列匹配類問題。
好的，接下來我們繼續(xù)介紹 不同的子序列（LeetCode題目115）的問題及其解法。
九、不同的子序列（LeetCode題目115）
題目描述
給定一個字符串s和一個字符串t，計算在s的子序列中t出現(xiàn)的個數(shù)。
示例
輸入: s = "rabbbit", t = "rabbit"
輸出: 3
解釋: 如下圖所示，有 3 種可以從 s 中得到 "rabbit" 的方式。
解題思路：
在該題中，我們需要統(tǒng)計t在s中作為子序列出現(xiàn)的次數(shù)。可以使用動態(tài)規(guī)劃，通過分析字符是否匹配，遞推出每個子問題的解。具體步驟如下：
- dp數(shù)組定義：定義
dp[i][j]為s的前i個字符中t的前j個字符出現(xiàn)的次數(shù)。 - 狀態(tài)轉(zhuǎn)移方程：
- 當
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]，表示字符不匹配的情況下，只能通過忽略當前字符來求解。
- 當
- 初始化：
dp[i][0] = 1，即t為空時，是任何字符串的子序列，子序列出現(xiàn)次數(shù)為1。 - 遞歸順序：按行遍歷
dp表，以自頂向下、自左向右的順序填充。
Go 語言代碼實現(xiàn)
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個字符的子序列個數(shù)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]
}
關(guān)鍵要點分析：
- 該題的動態(tài)規(guī)劃表格通過字符匹配與否，確保了子序列匹配的所有可能組合都被考慮。
- 通過逐層累積每一子問題的最優(yōu)解，
dp[ls][lt]即為s中出現(xiàn)t的所有方式。
十、兩個字符串的刪除操作（LeetCode題目583）
接下來，我們將探討兩個字符串的刪除操作這一問題，該題的本質(zhì)是在兩個字符串之間尋找相似部分，從而最小化刪除次數(shù)。
題目描述
給定兩個單詞word1和word2，返回使得兩個單詞相同所需的最小步數(shù)。每步可以刪除任意一個字符串中的一個字符。
示例
輸入: word1 = "sea", word2 = "eat"
輸出: 2
解釋: 將 "sea" 變?yōu)?"ea" 并刪除 "t"，最少需要 2 步。
解題思路：
該題的核心在于最小化兩個字符串的刪除操作，具體實現(xiàn)可以通過找到最長公共子序列來進行。步驟如下：
- dp數(shù)組定義：定義
dp[i][j]為將word1的前i個字符與word2的前j個字符變?yōu)橄嗤璧淖钚〔綌?shù)。 - 狀態(tài)轉(zhuǎn)移方程：
- 當
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。
- 當
- 初始化：
dp[i][0] = i，表示word2為空時，需要刪除word1的所有字符；同理，dp[0][j] = j。 - 遞歸順序：從左到右逐步構(gòu)建二維
dp表。
Go 語言代碼實現(xiàn)
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)橄嗤璧淖钚〔綌?shù)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]
}// 工具函數(shù)：返回兩個整數(shù)中的較小值
func min(a, b int) int {if a < b {return a}return b
}
關(guān)鍵要點分析：
- 該問題可以看作是“編輯距離”的簡化版，主要涉及刪除操作，因此只需考慮刪除的最小代價。
dp[i][j]記錄了當前最小步數(shù)，并通過累積前面的最小操作實現(xiàn)了從局部最優(yōu)解推向全局最優(yōu)解。
十一、編輯距離（LeetCode題目72）
編輯距離是經(jīng)典的動態(tài)規(guī)劃問題之一，主要關(guān)注插入、刪除和替換操作的最小代價。
題目描述
給定兩個單詞word1和word2，計算將word1轉(zhuǎn)換成word2所需的最小操作數(shù)?？梢詫σ粋€單詞執(zhí)行插入、刪除或替換操作。
示例
輸入: word1 = "horse", word2 = "ros"
輸出: 3
解釋: horse -> rorse (替換 'h' 為 'r') -> rose (刪除 'r') -> ros (刪除 'e')
解題思路：
該問題可通過動態(tài)規(guī)劃解決，逐步最小化每次編輯的代價：
- dp數(shù)組定義：
dp[i][j]為將word1的前i個字符變?yōu)?code>word2的前j個字符所需的最小編輯次數(shù)。 - 狀態(tài)轉(zhuǎn)移方程：
- 如果
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。
- 如果
- 初始化：當
word2為空時，dp[i][0] = i；同理，dp[0][j] = j。 - 遞歸順序：逐步填充整個
dp表，從左到右、從上到下。
Go 語言代碼實現(xiàn)
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個字符的最小編輯次數(shù)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]
}// 工具函數(shù)：返回三個整數(shù)中的最小值
func min(a, b, c int) int {if a < b {if a < c {return a}return c}if b < c {return b}return c
}
關(guān)鍵要點分析：
- 本題動態(tài)規(guī)劃的核心在于清晰的狀態(tài)轉(zhuǎn)移方程，將字符是否匹配的三種編輯操作的最小代價逐步遞推。
dp[i][j]通過三種操作的最小代價累積，得出將word1轉(zhuǎn)換成word2所需的最小編輯距離。
好的，接下來我們繼續(xù)介紹 回文子串（LeetCode題目647）的問題及其解法。
十二、回文子串（LeetCode題目647）
題目描述
給定一個字符串s，計算并返回s中的回文子串數(shù)量。具有相同順序且相同字符的子串稱為回文。
示例
輸入: s = "abc"
輸出: 3
解釋: 回文子串為 ["a","b","c"]。
輸入: s = "aaa"
輸出: 6
解釋: 回文子串為 ["a","a","a","aa","aa","aaa"]。
解題思路：
這道題要求我們統(tǒng)計字符串中的回文子串數(shù)量，可以利用動態(tài)規(guī)劃來判斷每個子串是否為回文，并記錄回文的數(shù)量。
- dp數(shù)組定義：定義
dp[i][j]表示從字符s[i]到s[j]的子串是否是回文子串。若為回文子串，則dp[i][j] = true，否則為false。 - 狀態(tài)轉(zhuǎn)移方程：
- 當
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。
- 當
- 初始化：長度為1的子串均為回文，因此對每個位置
i，dp[i][i] = true。 - 遞歸順序：從右下角向左上角遍歷
dp數(shù)組，逐步填充。
Go 語言代碼實現(xiàn)
func countSubstrings(s string) int {l := len(s)dp := make([][]bool, l) // dp[i][j]表示s從i到j(luò)的子串是否為回文for i := range dp {dp[i] = make([]bool, l)}result := 0 // 用于記錄回文子串的數(shù)量for i := l - 1; i >= 0; i-- { // 從右下角到左上角填充dp數(shù)組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++ // 每找到一個回文子串就計數(shù)加一}}}return result
}
關(guān)鍵要點分析：
- 狀態(tài)轉(zhuǎn)移方程
dp[i][j]結(jié)合字符相等性和內(nèi)部子串的回文性有效判斷了每個子串的回文性質(zhì)。 - 遍歷順序為從右下角到左上角，保證每個較短子串的狀態(tài)在較長子串狀態(tài)確定前已完成更新。
十三、最長回文子序列（LeetCode題目516）
最后，我們來看一道回文序列問題，要求在一個字符串中找到最長的回文子序列長度。
題目描述
給定一個字符串s，找到其中最長的回文子序列的長度。子序列不要求是連續(xù)的，但順序必須保持一致。
示例
輸入: s = "bbbab"
輸出: 4
解釋: "bbbb" 是最長的回文子序列。
解題思路：
該問題可以使用動態(tài)規(guī)劃通過遞歸判斷字符的對稱性來解決。
- dp數(shù)組定義：定義
dp[i][j]為字符串s從位置i到j的子串的最長回文子序列長度。 - 狀態(tài)轉(zhuǎn)移方程：
- 若
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])。
- 若
- 初始化：對于每個位置
i，dp[i][i] = 1，即單個字符的回文長度為1。 - 遞歸順序：從下到上、從左到右填充
dp數(shù)組，保證子問題優(yōu)先求解。
Go 語言代碼實現(xiàn)
func longestPalindromeSubseq(s string) int {l := len(s)dp := make([][]int, l) // dp[i][j]表示s從i到j(luò)的最長回文子序列長度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] // 返回整個字符串的最長回文子序列長度
}// 工具函數(shù)：返回兩個整數(shù)中的最大值
func max(a, b int) int {if a > b {return a}return b
}
關(guān)鍵要點分析：
- 本題通過遞歸狀態(tài)方程有效地判斷了字符對稱性，
dp[i][j]記錄每個子問題的最優(yōu)解，保證子問題遞推到全局。 - 本題與最長回文子串問題不同，最長回文子序列并不要求子序列連續(xù)，狀態(tài)轉(zhuǎn)移時依賴左、下和左下角元素。
十四、結(jié)論
在本篇文章中，我們系統(tǒng)地梳理了LeetCode中一系列子序列類問題的動態(tài)規(guī)劃解法。通過dp數(shù)組定義、狀態(tài)轉(zhuǎn)移方程設(shè)計、初始化、遞歸順序等方面，我們展示了如何構(gòu)建并解決常見的子序列問題。動態(tài)規(guī)劃不僅要求細致的代碼實現(xiàn)，更強調(diào)對問題的整體分解與子問題的遞推組合，這些方法論將有助于提升算法的解決能力。希望本文對您深入理解和掌握動態(tài)規(guī)劃有所幫助！
