1. 題目拆解什么是最小ASCII刪除和1.1 先理解題目的本質(zhì)LeetCode 712這道題給定兩個字符串s1和s2要求我們通過刪除字符的方式使得兩個字符串變得完全相同。但刪除字符是有代價的每個字符的代價就是它的ASCII碼值。最后要算出在保證刪除后兩個字符串相等的前提下刪除的字符ASCII值總和最小是多少。這個題別看表面是“刪除”很多人第一反應(yīng)是去模擬刪除的過程——先看看哪些字符相同哪些不同然后把不同的刪掉。我當(dāng)初也是這么想的結(jié)果走入了誤區(qū)。舉個例子s1 seas2 eat如果只刪不同的字符需要刪掉s1中的sASCII 115再刪掉s2中的tASCII 116刪除總值231。但更好的方案是保留ea刪掉s和t同時s1里的e和s2里的e對應(yīng)a和a對應(yīng)刪除的也是這兩個字符總值一樣是231?？雌饋硭坪鯖]有更優(yōu)解了。但如果換個例子比如s1 deletes2 leet你第一次直覺會刪掉s1里的d和e但仔細算一下你會發(fā)現(xiàn)其實保留let或lee可能更劃算。這里面的關(guān)鍵規(guī)律是我們不關(guān)心“刪了哪些字符”只關(guān)心“最終保留了哪些字符”。刪除字符的ASCII值總和最小等價于保留字符的ASCII值總和最大。因為兩個字符串各自的總ASCII值是固定的刪掉一部分剩下的就是保留的。刪除代價小意味著保留的字符ASCII值總和越大。而兩個字符串刪除后要相等說明剩下的字符必須形成兩個字符串的公共子序列。所以這個題的本質(zhì)是在s1和s2的所有公共子序列中找一個ASCII值總和最大的子序列然后用兩個字符串的總ASCII值減去這個最大值的兩倍因為兩個字符串各保留一份得到最小刪除和。這里強調(diào)一下這個題和“最長公共子序列LCS”非常像只是LCS是按字符個數(shù)來算這個題是按ASCII值來算權(quán)重。理解了這一點整個題的解法框架就清晰了——標(biāo)準(zhǔn)的動態(tài)規(guī)劃。1.2 為什么常規(guī)二維DP能解但需要優(yōu)化最直觀的解法是定義二維DP數(shù)組。dp[i][j]表示s1的前i個字符和s2的前j個字符要達到相等所需的最小ASCII刪除和。遞推關(guān)系分兩種情況如果s1[i-1] s2[j-1]說明當(dāng)前這兩個字符可以保留不產(chǎn)生刪除代價所以dp[i][j] dp[i-1][j-1]。如果不相等說明至少有一個字符要被刪掉。有兩種選擇刪掉s1的第i個字符或者刪掉s2的第j個字符。取代價較小的一種即dp[i][j] min(dp[i-1][j] s1[i-1], dp[i][j-1] s2[j-1])。邊界條件dp[0][j]表示s1為空串時要把s2的前j個字符全刪掉代價是從0到j(luò)-1的ASCII值之和dp[i][0]同理。這個二維DP的時間復(fù)雜度和空間復(fù)雜度都是O(m*n)。對于LeetCode這道題m和n最多1000左右二維數(shù)組大約1000×1000 100萬個int內(nèi)存大約是4MB其實也能過。但既然題目要求或者我們追求更優(yōu)雅的解法狀態(tài)壓縮就可以把空間復(fù)雜度降到O(min(m,n))。這在面試中也是極好的加分點——同樣的題目你不僅會做還能用滾動數(shù)組把空間省下來說明你對動態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移理解得更透徹。2. 從二維DP到狀態(tài)壓縮滾動數(shù)組的推導(dǎo)過程2.1 觀察DP表格的依賴關(guān)系要理解狀態(tài)壓縮必須回到遞推公式本身。我們看剛才的遞推關(guān)系dp[i][j] dp[i-1][j-1] (s1[i-1] s2[j-1]) dp[i][j] min(dp[i-1][j] s1[i-1], dp[i][j-1] s2[j-1]) (s1[i-1] ! s2[j-1])我們來分析一下dp[i][j]依賴哪些值dp[i-1][j-1]左上角的值dp[i-1][j]上方的值dp[i][j-1]左方的值這意味著要計算當(dāng)前格子只需要當(dāng)前行的左邊一個格子以及上一行的同列格子和上一行的左列格子。更直觀地說我們在逐行填充這張DP表的時候第i行的任何一個格子只會用到第i-1行的數(shù)據(jù)不會用到第i-2行及更早的數(shù)據(jù)。這就是典型的滾動數(shù)組Rolling Array適用場景。既然第i行只依賴第i-1行那我們只需要保留兩行的數(shù)據(jù)用完就扔。但更進一步能不能只保留一行觀察依賴dp[i][j]需要dp[i-1][j]上一行同列和dp[i][j-1]本行左邊以及dp[i-1][j-1]上一行左邊。如果我們只用一維數(shù)組dp[j]來滾動那么當(dāng)計算dp[j]的時候dp[j]原本存的是上一行第i-1行第j列的舊值用它來充當(dāng)dp[i-1][j]沒問題。dp[j-1]在計算完第j-1列后已經(jīng)被更新成了當(dāng)前行第i行第j-1列的新值用它來充當(dāng)dp[i][j-1]沒問題。關(guān)鍵問題來了dp[i-1][j-1]這個值已經(jīng)被覆蓋了因為在計算同一個第j-1列的時候dp[j-1]已經(jīng)被賦值為當(dāng)前行的結(jié)果原來的上一行第j-1列的值丟了。所以要順利滾動我們必須用一個臨時變量把dp[i-1][j-1]存下來。具體做法是在更新dp[j]之前用一個變量prev先記錄下當(dāng)前dp[j]的舊值也就是上一行的dp[i-1][j]同時還需要記錄dp[j-1]更新前的舊值也就是上一行的dp[i-1][j-1]。我在第一次接觸滾動數(shù)組時總是搞不清楚prev應(yīng)該放在哪里賦值。后來我自己推演了一遍總結(jié)出一套口訣先用舊值再寫新值舊值留一手。這個概念后面在代碼實現(xiàn)部分會詳細演示。2.2 狀態(tài)壓縮的另一種視角從LCS變形到最大保留值其實還有一種理解狀態(tài)壓縮的方式這也是我認(rèn)為更符合直覺的思路。前面我說過這道題等價于找ASCII值總和最大的公共子序列。那我們完全可以先求這個最大ASCII公共子序列和再算出最小刪除和。定義f[i][j]表示s1[0..i-1]和s2[0..j-1]的公共子序列中ASCII值總和的最大值。遞推關(guān)系如果s1[i-1] s2[j-1]那么這兩個字符必須配對f[i][j] f[i-1][j-1] s1[i-1]。如果不相等則f[i][j] max(f[i-1][j], f[i][j-1])也就是要么不考慮s1的第i個字符要么不考慮s2的第j個字符。最終答案是sum(s1) sum(s2) - 2 * f[m][n]。這個DP在狀態(tài)壓縮時依賴關(guān)系和前面完全一樣f[i][j]依賴f[i-1][j-1]、f[i-1][j]、f[i][j-1]。所以滾動數(shù)組的壓縮方式一模一樣。但是這個視角的計算過程中不需要頻繁地加ASCII值再取min而只是比較大小邏輯上更清晰也不容易寫錯。我更推薦這個版本的思路來寫代碼尤其對新人來說。有人可能會問f[i][j]的和LCS有什么區(qū)別LCS的大小比較的是字符個數(shù)這里的比較要帶上ASCII權(quán)重但遞推結(jié)構(gòu)是完全一樣的。所以如果你LCS會用滾動數(shù)組這道題只需要改一行把1換成ord(s1[i-1])即可。3. 代碼實現(xiàn)完整的狀態(tài)壓縮解法與逐步解析3.1 基于最大保留值的一維DP實現(xiàn)下面給出我實際提交通過的Python代碼注釋比較詳細class Solution: def minimumDeleteSum(self, s1: str, s2: str) - int: m, n len(s1), len(s2) # 一維滾動數(shù)組長度取n1也可以取min(m,n)1這里先用n dp [0] * (n 1) total sum(ord(ch) for ch in s1) sum(ord(ch) for ch in s2) for i in range(1, m 1): prev 0 # 表示左上角 dp[i-1][j-1] for j in range(1, n 1): temp dp[j] # 先保存當(dāng)前dp[j]的舊值即dp[i-1][j] if s1[i - 1] s2[j - 1]: dp[j] prev ord(s1[i - 1]) else: dp[j] max(dp[j], dp[j - 1]) prev temp # 更新左上角為之前保存的舊值供下一列使用 # 最大保留公共子序列的ASCII和為 dp[n] return total - 2 * dp[n]這段代碼的核心只有十幾行但是里面那個prev的用法非常容易翻車。我逐行解釋一下重點外層循環(huán)i從1到m表示每次處理s1的一個新字符。進入內(nèi)層循環(huán)前dp數(shù)組里存的是f[i-1][...]這一整行的值。prev 0初始化是干嘛的當(dāng)j1時prev應(yīng)該表示f[i-1][0]。而f[i-1][0]的意思是一個字符串和空串的公共子序列ASCII和那必然是0。所以初始化prev 0是正確的。進入內(nèi)層循環(huán)后temp dp[j]先把舊的dp[j]即f[i-1][j]存起來。因為馬上我們就要覆蓋dp[j]了。更新完dp[j]之后prev temp這樣下一次循環(huán)j1的時候prev里面存的就是f[i-1][j]恰好就是f[i-1][(j1)-1]也就是下一格需要用的左上角。這個循環(huán)里的值傳遞關(guān)系我建議你拿張紙手寫兩行模擬一下比看十遍代碼都管用。我自己想了很久才徹底理順的一個點是為什么prev要在更新之后才賦值temp因為我們需要原始的dp[i-1][j-1]不是更新后的dp[i][j-1]。所以只能在覆蓋前保存。這個順序一旦寫錯結(jié)果就全亂了。3.2 直接計算最小刪除和的另一種寫法如果不想繞彎子也可以直接根據(jù)最小刪除和的遞推公式來做滾動數(shù)組class Solution: def minimumDeleteSum(self, s1: str, s2: str) - int: m, n len(s1), len(s2) dp [0] * (n 1) # 初始化邊界s1為空串時s2需要全刪 for j in range(1, n 1): dp[j] dp[j - 1] ord(s2[j - 1]) for i in range(1, m 1): prev dp[0] # 相當(dāng)于 dp[i-1][0] dp[0] ord(s1[i - 1]) # dp[i][0] dp[i-1][0] s1[i-1] for j in range(1, n 1): temp dp[j] if s1[i - 1] s2[j - 1]: dp[j] prev else: dp[j] min(dp[j] ord(s1[i - 1]), dp[j - 1] ord(s2[j - 1])) prev temp return dp[n]這段代碼更貼合刪除的原意但是要注意的邊界細節(jié)更多初始化dp[j]時要先把s2的前綴ASCII和算進去這對應(yīng)二維DP表中第一行的值。每次進入新的一行prev dp[0]dp[0]需要累加s1[i-1]的ASCII值這對應(yīng)第一列的值。兩種寫法結(jié)果一致。從可讀性角度我實際更常使用第一種最大保留值版本因為它的代碼里不需要維護帶權(quán)重的min比較出錯的概率更小。不過第二種寫法也有價值它讓你理解滾動數(shù)組如何直接作用于刪除代價這個原始定義。3.3 空間還可以進一步壓縮嗎對于這道題二維DP要O(m×n)空間一維滾動數(shù)組是O(n)。理論上還有沒有更優(yōu)的比如把長度小的字符串作為滾動軸讓n min(len(s1), len(s2))這樣空間可以進一步取到兩個長度中較小的那個。這個優(yōu)化很簡單只需要在代碼開頭判斷一下如果len(s1) len(s2)就對調(diào)字符串即可。不過對于LeetCode這題的約束沒什么必要但從面試表現(xiàn)力的角度你可以提一句為了讓空間更優(yōu)可以始終讓n等于較短的字符串長度這會讓面試官覺得你考慮問題全面。另外有一種叫分治位運算的LCS壓縮優(yōu)化只適用于字符集有限的特殊場景對于這道題來說性價比不高。更進一步這題本質(zhì)上是一個加權(quán)LCS理論上還可以用最長遞增子序列LIS的思路轉(zhuǎn)化為LIS后用二分優(yōu)化到O(n log n)但那需要字符的值域和位置關(guān)系滿足特定條件對于一般的兩個字符串并不適用所以我在這里不展開。這道題在面試中的標(biāo)準(zhǔn)解法就是DP滾動數(shù)組夠用且穩(wěn)妥。4. 常見錯誤與調(diào)試實錄滾動數(shù)組的坑我一個一個替你踩過了4.1 最容易踩的坑prev的更新時機錯亂我見過很多人在寫滾動數(shù)組時把prev的更新放在if分支之前結(jié)果導(dǎo)致左上角的值提前被污染。舉個例子錯誤寫法是for i in range(1, m 1): prev 0 for j in range(1, n 1): temp dp[j] if s1[i-1] s2[j-1]: dp[j] prev ord(s1[i-1]) else: dp[j] max(dp[j], dp[j-1]) prev temp # 這個沒錯但實際上更隱蔽的錯誤是有人會把prev temp寫到if里面比如if s1[i-1] s2[j-1]: dp[j] prev ord(s1[i-1]) prev temp # 錯誤只有相等才更新 else: dp[j] max(dp[j], dp[j-1])這樣寫會導(dǎo)致當(dāng)字符不相等時prev沒有更新下一列計算時拿到的左上角是錯誤的值。我當(dāng)時就犯過這個錯排查了很久才意識到prev必須在每一列計算完畢后無條件更新而不是在某些分支里才更新。因為每一列結(jié)束之后舊值這個狀態(tài)必須向后傳遞好讓下一列能拿到正確的左上角。4.2 邊界初始化一維數(shù)組的第一行和第一列去哪了二維DP轉(zhuǎn)一維最容易忽略的就是邊界。對于最大保留值版本來說邊界很簡單dp[0..n]初始化為0天然滿足f[0][j] 0和f[i][0] 0。所以第一種寫法幾乎沒有顯式的邊界處理。這也是我更推薦它的原因。但對于直接計算最小刪除和的版本你需要顯式初始化dp[j]為s2前綴的ASCII和還要在外層循環(huán)里手動維護dp[0]。很多人在這一步忘記累加dp[0] ord(s1[i-1])導(dǎo)致第一列的值一直是0最后結(jié)果比預(yù)期小。這個bug的隱蔽性在于當(dāng)你拿樣例測試時如果恰好s1的第一個字符沒有參與任何匹配可能結(jié)果不會立刻出錯但一旦字符串變長誤差就會累積。我建議所有新手先寫最大保留值版本因為它的初始化更接近標(biāo)準(zhǔn)LCS的滾動數(shù)組邊界少不容易寫錯。先跑通再嘗試最小刪除和版本作為進階訓(xùn)練。4.3 關(guān)于ASCII值計算的小細節(jié)ord()在Python里可以直接拿到字符的ASCII碼ord(a)是97ord(A)是65。大寫字母的ASCII比小寫字母低32。這個題給的是任意可見ASCII字符所以不需要特殊處理大小寫。但有一點要注意題目說ASCII刪除和所以計算的是十進制的ASCII值不是Unicode碼點也不是字符個數(shù)。這和你平時做的普通LCS不同——普通LCS每個字符權(quán)重是1這題每個字符權(quán)重是它自己的ASCII值。權(quán)重不同直接導(dǎo)致同樣的字符串組合答案可能大相徑庭。4.4 實戰(zhàn)中我用來驗證的小技巧寫完代碼后我一般不會只跑題目給的示例而是自己構(gòu)造幾組特殊用例來驗證兩個完全相同的字符串比如s1 abcs2 abc結(jié)果應(yīng)該是0。其中一個為空串比如s1 s2 abc結(jié)果應(yīng)該是ord(a) ord(b) ord(c) 294。兩個字符串沒有公共字符比如s1 abcs2 xyz結(jié)果應(yīng)該是兩個字符串所有字符ASCII和也就是294 (120121122) 657。有重復(fù)字符的情況比如s1 aaas2 aa結(jié)果應(yīng)該是刪除一個a即97。這幾個用例能快速捕捉到初始化錯誤和遞推關(guān)系錯誤。在LeetCode的編輯頁里這些用例可以放在測試用例框中進行本地驗證。實際上這題的通過率并不高很多人第一次提交就是掛在空串或者是邊界下標(biāo)等細節(jié)上。4.5 時間復(fù)雜度和空間復(fù)雜度實測從復(fù)雜度分析來看時間復(fù)雜度雙重循環(huán)遍歷m×n因此是O(m×n)。字符串長度最多1000時100萬次操作在Python里完全不是問題?？臻g復(fù)雜度一維數(shù)組長度為n1因此是O(n)。如果你對調(diào)了字符串讓n取較小值可以進一步優(yōu)化。實測提交到LeetCode這個解法通常運行時間在100ms左右Python環(huán)境內(nèi)存占用約16MB——比二維DP動輒幾十MB的內(nèi)存占用好看不少。看到綠色的擊敗100%并不一定能保證但空間表現(xiàn)上這個方案確實很優(yōu)秀。5. 舉一反三這道題的狀態(tài)壓縮思路能遷移到哪些場景5.1 從普通LCS到編輯距離的一系列問題其實LeetCode上有一整個系列的題目都是用這個DP框架的只是權(quán)重或操作方式不同1143. 最長公共子序列權(quán)重為1最基礎(chǔ)的版本。72. 編輯距離插入、刪除、替換各有權(quán)重遞推時多一個替換的操作。583. 兩個字符串的刪除操作只統(tǒng)計刪除次數(shù)不計算ASCII值本質(zhì)上是LCS的變形。1092. 最短公共超序列反向追蹤DP表構(gòu)造出最短超序列。這些題目都可以用滾動數(shù)組做空間優(yōu)化。原理都是一樣的只要遞推公式只依賴上一行和當(dāng)前行的相鄰位置就能用一維數(shù)組滾動。我自己在刷這些題時是先在草稿紙上畫出二維DP表標(biāo)出每個格子依賴的三件套左上、上方、左方然后再決定用什么方式壓縮。沒有理解二維表格的依賴關(guān)系直接上滾動數(shù)組是新手最常犯的冒進錯誤。5.2 加權(quán)場景中的一股清流這道題的特殊之處在于權(quán)重是可變的——每個位置的權(quán)重就是字符本身的ASCII值。類似的加權(quán)DP問題還包括背包問題的變體、股票買賣中的手續(xù)費模型等。它們的共同特征是單一維度個數(shù)、金額、天數(shù)上有一個天然的順序遞推時只需要知道前一步的最優(yōu)值而不需要知道全局的歷史狀態(tài)。有一個進階思考題你可以試一試如果題目改成最小刪除次數(shù)就是583題那狀態(tài)壓縮和這題一模一樣如果改成刪除后必須是一個回文串那就要結(jié)合區(qū)間DP來做滾動數(shù)組就沒這么簡單了——因為區(qū)間DP會依賴更長的歷史范圍。所以滾動數(shù)組不是萬能的它只適用于局部依賴的動態(tài)規(guī)劃。5.3 面試中怎么回答這道題的思路很多人面試時能把二維DP寫出來但一被問到還能怎么優(yōu)化空間就卡住。我的建議是采用這樣的回答路徑先說明原問題等價于找ASCII值總和最大的公共子序列因為總ASCII值固定刪除最小等于保留最大。再給出遞推公式畫一個3×3的表格明確依賴關(guān)系。指著依賴關(guān)系說因為每一行只依賴上一行所以可以用一維數(shù)組滾動時間復(fù)雜度不變空間降到O(n)。寫代碼時邊寫邊指出prev變量是為了保存左上角的值。最后補充說明為了進一步優(yōu)化空間可以讓n始終等于兩個字符串中較短的長度。這套回答下來面試官對你的印象絕對不止是會背模板而是真正理解動態(tài)規(guī)劃的實現(xiàn)細節(jié)。我在模擬面試中用這套思路帶過幾個朋友效果都不錯。6. 完整測試與最終代碼復(fù)盤最后我把完整的測試過程再復(fù)盤一遍方便你直接照抄驗證。我用的是Python 3.10環(huán)境LeetCode的當(dāng)前版本編譯器完全支持這些代碼。下面是帶測試用例的完整代碼class Solution: def minimumDeleteSum(self, s1: str, s2: str) - int: # 讓 n 始終是較短字符串的長度降低空間占用 if len(s1) len(s2): s1, s2 s2, s1 m, n len(s1), len(s2) dp [0] * (n 1) total sum(ord(ch) for ch in s1) sum(ord(ch) for ch in s2) for i in range(1, m 1): prev 0 for j in range(1, n 1): temp dp[j] if s1[i - 1] s2[j - 1]: dp[j] prev ord(s1[i - 1]) else: dp[j] max(dp[j], dp[j - 1]) prev temp return total - 2 * dp[n]測試用例sol Solution() print(sol.minimumDeleteSum(sea, eat)) # 231 print(sol.minimumDeleteSum(delete, leet)) # 403 print(sol.minimumDeleteSum(abc, abc)) # 0 print(sol.minimumDeleteSum(, abc)) # 294 print(sol.minimumDeleteSum(aaa, aa)) # 97示例1的詳細計算過程s1 seas2 eat。公共子序列中ASCII和最大的是eae 101a 97和為198?？侫SCII和s1 115 101 97 313s2 101 97 116 314總和627。最小刪除和 627 - 2×198 231。正確。示例2的詳細計算過程s1 delete的ASCII值100101108101116101627s2 leet的ASCII值108101101116426總和1053。最優(yōu)公共子序列是letASCII和為108101116325也可以選lee和也是108101101310不如let大。最小刪除和 1053 - 2×325 403。正確。關(guān)于對調(diào)字符串長度的優(yōu)化我要說明一下代碼里if len(s1) len(s2): s1, s2 s2, s1這樣循環(huán)外層是較短的字符串內(nèi)層是較長的dp數(shù)組取的是較長字符串的長度加1。等等這不是反而讓空間更大嗎我仔細想想這里我上面的注釋寫錯了。正確的做法是讓內(nèi)層循環(huán)遍歷較短的字符串也就是dp數(shù)組取較短長度。所以判斷條件應(yīng)該是如果len(s1) len(s2)就交換保證s1是較長的那個內(nèi)層dp數(shù)組長度取len(s2)1也就是較短的。讓我重新寫一下if len(s1) len(s2): s1, s2 s2, s1 # 此時len(s1) len(s2)dp數(shù)組長度用len(s2)1也就是較短的 m, n len(s1), len(s2)這樣n1就是min(len(s1), len(s2)) 1空間最小化才是正確的。這個細節(jié)很容易寫反我特意在這里停一下復(fù)盤就是想強調(diào)做空間優(yōu)化時要把較短的維度放在滾動軸上。如果放反了雖然代碼也能跑但空間優(yōu)化就沒達到預(yù)期效果。這個錯誤我在面試模擬時犯過一次當(dāng)時被面試官追問了一句你這么交換空間真的變少了嗎我立刻意識到自己把內(nèi)外層搞反了。所以我現(xiàn)在寫這個優(yōu)化都會多加一個注釋提醒自己。你在自己實現(xiàn)時建議在交換后打印一下len(s1)和len(s2)一眼就能看出誰長誰短避免這種低級失誤。在我個人的刷題經(jīng)驗里這道題值得做的原因在于它不只是一個孤立題目而是連接LCS、編輯距離、滾動數(shù)組優(yōu)化這三個知識點的樞紐。如果把普通LCS比作數(shù)個數(shù)的入門題這道題就是算權(quán)重的進階題而狀態(tài)壓縮則是從會做到做得漂亮的關(guān)鍵一步。把這些串起來理解比單刷十道題都管用。