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