設為「置頂或星標」,第一時間送達乾貨。
轉自面向大象編程
本期例題:LeetCode 1143. Longest Common Subsequence 最長公共子序列(Medium)
給定兩個字符串 s 和 t,返回這兩個字符串的最長公共子序列的長度。若這兩個字符串沒有公共子序列,則返回 0。
一個字符串的子序列是指這樣一個新的字符串:它是由原字符串在不改變字符的相對順序的情況下刪除某些字符(也可以不刪除任何字符)後組成的新字符串。例如,"ace" 是 "abcde" 的子序列。
在上一篇文章中,我們以打家劫舍(House Robber)問題為例講解了動態規劃問題的一般解題步驟。不過,打家劫舍問題是一維動態規劃問題,而還有很多題目屬於二維動態規劃。今天我們就以一道經典的「最長公共子序列」問題講解二維動態規劃的解法。
最長公共子序列問題經典到什麼程度呢?經典到有自己的專用縮寫 —— LCS (Longest Common Subsequence)。如果你在別的地方看到 LCS 的縮寫,要能夠知道這是最長公共子序列的問題。
如果說打家劫舍問題是動態規劃的最佳入門題,那麼 LCS 問題就是二維動態規劃的最佳入門題,問題經典,方法典型。本文會在一步步求解 LCS 問題的過程中,講解二維動態規劃問題的解題要領。
本文假設你已經了解了打家劫舍問題的解法以及動態規劃問題的基本解題步驟。對此不是很清楚的同學可以回顧一下上一篇文章:
LeetCode 例題精講 | 14 打家劫舍問題:動態規劃的解題四步驟
一維與二維動態規劃首先我們要清楚一維動態規劃與二維動態規劃的含義。對於打家劫舍問題,我們定義
為什麼要區分子問題的維度呢?這是因為子問題的維度會直接影響 DP 數組的維度。二維的 DP 數組不僅空間複雜度變大,DP 數組的計算順序也更複雜。
一般來說,絕大多數動態規劃問題的維度不會超過二維。必須使用三維以上子問題的題目屬於難題,不需要掌握。
使用四步驟解題在上一篇文章中,我們講解了動態規劃題目的的四個基本解題步驟:
二維動態規劃問題同樣遵循這四個解題步驟,不過每個步驟可能會更複雜。下面我們使用四步驟方法一步步解決 LCS 問題。
步驟一:定義子問題要定義子問題,我們還是抓住這樣一個子問題的基本性質:子問題是和原問題相似,但規模較小的問題。
對於 LCS 問題,原問題是「s 和 t 的最長公共子序列」。那么子問題可以縮小字符串 s 或者 t 的規模,變成「s 的前
可以看到,子問題有
LCS 問題的子問題定義步驟二:寫出子問題的遞推關係這一步是求解動態規劃問題最關鍵的一步。二維的子問題有很多可能的遞推關係,有些題目一目了然,有些則可能需要仔細推敲。
一般來說,我們首先思考能不能使用一種最簡單的子問題遞推關係:看當前子問題和前一個子問題的關係。如果是一維子問題,就是看
LCS 問題的子問題
第一種情況:如果 s[i-1] == t[j-1] ,我們可以用這個字符作為最長公共子序列中的字符,然後找 s[0..i-1) 和 t[0..j-1) 的最長公共子序列,如下圖所示。
子問題的遞推關係,情況一第二種情況:如果 s[i-1] != t[j-1],我們可以試著刪掉 s 或者 t 末尾的一個字符,即比較 s[0..i-1) 與 t[0..j),或者比較 s[0..i) 與 t[0..j-1),兩種方案中,選擇較長的公共子序列,如下圖所示。
子問題的遞推關係,情況二這樣,我們得到的子問題遞推關係為:
我們還要注意寫出遞推關係的 base case。當
步驟三:確定 DP 數組的計算順序對於二維動態規劃問題,我們仍然要堅持使用 DP 數組,用自底向上的順序計算子問題。因為 DP 數組中的每一個元素都對應一個子問題,當子問題變成二維之後,DP 數組也需要是二維數組。在 DP 數組中,dp[i][j] 對應子問題
DP 數組與子問題的對應關係在上一篇打家劫舍問題的講解中,我們直接給出了 DP 數組應該從左向右計算的結論。對於一維動態規劃問題,我們可以憑直覺確定 DP 數組的計算順序。但是對於二維動態規劃問題,我們需要有一定的方法來思考 DP 數組的計算順序。
DP 數組計算順序的基本原則是:當我們計算一個子問題時,它所依賴的其他子問題應該已經計算好了。 根據這個原則,我們思考三點內容。
第一點:DP 數組的有效範圍是什麼? 設 s 的長度為
int[][] dp = new int[m+1][n+1];二維 DP 數組的整個正方形區域都是合法的。
第二點:base case 和原問題在 DP 數組中在什麼位置? 如下圖所示,base case 位於 DP 數組的最左側一列和最上方一行,而原問題則位於 DP 數組的右下角。
DP 數組中,base case 和原問題的位置第三點:DP 數組的子問題依賴方向是什麼? 觀察子問題的遞推關係,
DP 數組中子問題的依賴方向我們發現,子問題的依賴方向是向右、向下的,因此 DP 數組的計算順序也應該是從左到右、從上到下。也就是說我們應該以這樣的順序遍歷 DP 數組:
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
// 計算 dp[i][j] ...
}
}而循環裡面的內容,照著子問題的遞推關係填進去就可以了。這樣,我們的題解代碼可以很輕鬆地寫出來:
public int longestCommonSubsequence(String s, String t) {
if (s.isEmpty() || t.isEmpty()) {
return 0;
}
// 子問題:
// f(i, j) = s[0..i) 和 t[0..j) 的最長公共子序列
// f(0, *) = 0
// f(*, 0) = 0
// f(i, j) = f(i-1, j-1) + 1, if s[i-1] == t[j-1]
// max{ f(i-1, j), f(i, j-1) }, otherwise
int m = s.length();
int n = t.length();
int[][] dp = new int[m+1][n+1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 0;
} else {
if (s.charAt(i-1) == t.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}
}
return dp[m][n];
}上面的代碼中還寫了一大段關於子問題定義、子問題遞推關係的公式。在面試的時候,我們最好把這些東西都寫出來,一方面讓自己寫代碼有個參考,另一方面可以讓面試官理解自己的思路。
步驟四:空間優化(可選)二維動態規劃問題的 DP 數組變成了二維數組,空間複雜度更高了。因此,二維動態規劃問題也更值得進行空間優化,降低空間複雜度。
不過,二維動態規劃問題的空間優化有很多種方法,需要根據不同的情況靈活使用。空間優化的步驟是可選的,優化不優化都可以。後面我會專門寫一篇文章介紹各種空間優化的方法。
對於這道 LCS 題目,我直接給出空間優化後的代碼,使用一維數組 + 臨時變量,有興趣的小夥伴可以自己思考為什麼可以這麼優化。
public int longestCommonSubsequence(String s, String t) {
if (s.isEmpty() || t.isEmpty()) {
return 0;
}
int m = s.length();
int n = t.length();
int[] dp = new int[n+1]; // new 出的數組會默認初始化為 0
for (int i = 1; i <= m; i++) {
int temp = 0;
for (int j = 1; j <= n; j++) {
int dp_j;
if (s.charAt(i-1) == t.charAt(j-1)) {
dp_j = temp + 1;
} else {
dp_j = Math.max(dp[j], dp[j-1]);
}
temp = dp[j];
dp[j] = dp_j;
}
}
return dp[n];
}不過需要注意的是,空間優化方法只能優化空間複雜度,不能優化時間複雜度。例如 LCS 問題在空間優化前後的複雜度為:
總結本文用最長公共子序列(LCS)問題展示了二維動態規劃問題的基本解題思路。動態規劃問題無論一維二維,都離不開四個基本解題步驟,我們在解題的時候需要牢記這四步驟。
相比一維動態規劃,二維動態規劃最複雜的地方在於子問題的遞推關係與計算順序。LCS 問題作為入門題,DP 數組的計算順序還很常規,而後面的「區間 DP」和「背包 DP」問題將會使你腦洞大開。
很多二維動態規劃問題都可以看到 LCS 問題的影子。例如「編輯距離」問題,雖然推導方式不太一樣,但思路和子問題依賴方式都和 LCS 問題很像。再例如「最長回文子序列」問題,好像是把 LCS 問題的子問題依賴方向旋轉了一下。這些題型我們後面都會逐步講到。
推薦閱讀• LeetCode 例題精講 | 05 雙指針×鍊表問題:快慢指針• LeetCode 例題精講 | 01 反轉鍊表:如何輕鬆重構鍊表• LeetCode 例題精講 | 04 用雙指針解 Two Sum:縮減搜索空間• LeetCode 例題精講 | 14 打家劫舍問題:動態規劃的解題四步驟• 如何成為一個更好的程式設計師,或者說是學習者?給你七個建議!• 在拼多多上班,是一種什麼樣的體驗?我tm心態崩了呀!• 寫給小白,從零開始擁有一個酷炫上線的網站!
歡迎關注我的公眾號「五分鐘學算法」,如果喜歡,麻煩點一下「在看」~