LeetCode 例題精講 | 15 最長公共子序列:二維動態規劃的解法

2021-02-21 五分鐘學算法

設為「置頂或星標」,第一時間送達乾貨。

轉自面向大象編程

本期例題: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心態崩了呀!•   寫給小白,從零開始擁有一個酷炫上線的網站!

歡迎關注我的公眾號「五分鐘學算法」,如果喜歡,麻煩點一下「在看」~

相關焦點

  • LeetCode 例題精講 | 16 最大子數組和:子數組類問題的動態規劃技巧
    Maximum Length of Repeated Subarray 最長公共子數組(Medium)在前面的文章中,我們分別講解了一維和二維動態規劃問題的解題步驟與基本思路。不過,僅僅掌握基本步驟是不夠的。要想熟練做出動態規劃題目,還要掌握足夠的解題技巧。
  • 動態規劃求解最長公共子序列
    最長公共子序列最長公共子序列,英文為Longest Common Subsequence,縮寫LCS。一個序列,如果是某兩個或多個已知序列的最長子序列,則稱為最長公共子序列。另外,要注意的是最長公共子序列與最長公共子串不一樣,下面看一個例子就明白。有序列S1和S2,其中S1=hello,S2=hero。那麼最長公共子序列為heo,而最長公共子串為he。
  • 算法總結:最長上升子序列(LIS)
    最長上升子序列,英文名 Longest Increasing Subsequence,簡稱 LIS,在面試中屬於難度較大,但又非常高頻的題目。最長遞增子序列(https://leetcode-cn.com/problems/longest-increasing-subsequence/)總體思路如果你不知道最長上升子序列是什麼意思,也沒有做那道題,我——當然不會怪你 😊最長上升(遞增)子序列這道題是最最基本的,也是最常考的題了,其他題目都是由它衍生而來。
  • [LeetCode] 1143. Longest Common Subsequence 最長公共子序列
    Constraints:這道題讓求最長相同的子序列,注意是子序列,不是子串,所以字符並不需要相連,但是字符順序還是需要保持的。LeetCode 之前也有題目需要藉助求 LCS 來解題,比如 Delete Operation for Two Strings,當時博主還疑惑怎麼 LeetCode 中沒有專門求 LCS 的題呢,這不,終於補上了。
  • 詳解最長公共子序列問題,秒殺三道動態規劃題目
    動態規劃系列問題也是一樣,尤其是子序列相關的問題。本文從「最長公共子序列問題」展開,總結三道子序列問題,解這道題仔細講講這種子序列問題的套路,你就能感受到這種思維方式了。最長公共子序列計算最長公共子序列(Longest Common Subsequence,簡稱 LCS)是一道經典的動態規劃題目,大家應該都見過:給你輸入兩個字符串s1和s2,請你找出他們倆的最長公共子序列,返回這個子序列的長度。
  • 動態規劃解最長公共子序列問題
    1 最長公共子序列問題概述1.1 問題定義序列2 動態規劃求解最長公共子序列問題    int** C=nullptr;    //輔助矩陣    int** src=nullptr;    //使用動態規劃方法計算C矩陣和src矩陣    void writeTable(Seq* seq1,Seq* seq2);    //使用回溯方法來得到所有的最長公共子序列    void createSubSeq(Seq*
  • LeetCode 例題精講 | 14 打家劫舍問題:動態規劃的解題四步驟
    動態規劃可能被很多同學奉為最難理解的算法題類型,因為它的解法很靈活,變化很多。但是動態規劃又經常作為筆試題的壓軸,我們不得不去面對它。其實,動態規劃是一類很講究「觸類旁通」的題型。很多動態規劃的解法需要你做過某一類型的例題,再做類似的題目的時候就可以想起來相應的思路。
  • 深入理解動態規划算法 | 最長公共子序列LCS
    那麼什麼情況下需要構建二元函數來求解動態規劃問題呢?本文將為大家介紹一個二元函數的求解問題。最長公共子序列Longest Common Subsequence即(LCS)問題指的是求解兩個序列的最長公共子序列及其長度。
  • 動態規劃刷題篇(1) 斐波那契、爬樓梯、路徑與最長遞增子序列
    這題就引出了動態規劃中的一個重要概念:DP數組。DP數組是用來存儲當前問題的子問題的這樣一個數組。動態規劃的核心就在於:當前問題可以分解為幾個子問題。最長遞增子序列給你一個整數數組 nums ,找到其中最長嚴格遞增子序列的長度
  • LeetCode-4-動態規劃
    最長上升子序列連結:https://leetcode-cn.com/problems/longest-increasing-subsequence/給定一個無序的整數數組,找到其中最長上升子序列的長度。
  • 經典動態規劃問題:最長公共/遞增子序列
    今天我們一起來看一下兩個僅有一"字"之差的經典的動態規劃問題:最後我們會以一道LeetCode題目為例子,看看如何在特定情況下把LCS歸約成LIS從而降低時間複雜度。在講具體問題之前我們先來舉個例子看一下什麼是子序列(subsequence)以及它和子數組(subarray)和子集(subset)之間的區別。
  • 算法精析:10隻白鼠試喝千瓶水1瓶有毒與最長公共子序列(串)
    四、最長公共子序列(串)算法題目:首先,最長公共子序列(LCS)及最長公共子串(LCSubstr)的定義:a="ABCGEUA"b="C五、最長公共子序列(串)算法思維分析這是一道考察動態規劃在算法中應用的題目,面試中很常見,也是一道經典的算法題。如果沒有見過類似題目的人,可能覺得有點難度。以下為思維線索分析(如果已經有所了解,請跳過):1、求最長公共子序列及子串,可用使用暴力破解法。
  • 經典算法研究總結(5)-動態規划算法解最長公共子序列LCS問題
    分析:求最長公共子序列(Longest Common Subsequence, LCS)是一道非常經典的動態規劃題,因此一些重視算法的公司像MicroStrategy都把它當作面試題。    事實上,最長公共子序列問題也有最優子結構性質。
  • Leetcode-128.最長連續子序列 精解
    今天我們會為大家介紹一道算法題,最長連續序列,這道題目曾作為原題出現在字節跳動二面上。在介紹完這道題目之後,我們會介紹一道解題方法上上與第一題有關聯,但難度上更勝一籌的騰訊筆試題。首先是第一題,最長連續子序列。Leetcode-128.最長連續子序列給定一個未排序的整數數組,找出最長連續序列的長度。
  • Java動態規划算法策略
    Dynamic Programming是五大常用算法策略之一,簡稱DP,譯作中文是「動態規劃」,可就是這個聽起來高大上的翻譯坑苦了無數人,因為看完這個算法你可能會覺得和動態規劃根本沒太大關係,它對「動態」和「規劃」都沒有太深的體現。
  • 列印出最長的公共子序列(LCS)
    在前一課中,我們討論了最長公共子序列(LCS)問題,並且討論了如何計算兩個序列的LCS的長度,但是沒有輸出具體的LCS序列。在本課中,我們討論了如何構造和輸出LCS具體序列。【問題】給定兩個序列,請找出兩個序列中存在的最長公共子序列(LCS)。注意:子序列由原序列中的子元素組成,這些子元素的次序與它們在原序列中出現的次序一樣,但不一定連續。
  • 雖然你看過,但就是寫不出來系列-最長上升(下降)子序列並輸出子序列
    任何疑問、意見、建議請公眾號留言或聯繫qq474356284    給定一個無序的整數數組,找到其中最長上升子序列的長度。
  • Leetcode刷題-動態規劃
    本文對leetcode上部分動態規劃問題進行分析並用python實現5. 最長回文子串 題目描述給定一個字符串 s,找到 s 中最長的回文子串。你可以假設 s 的最大長度為 1000。示例 2:思路1:分類討論這裡我們用dp存儲以每個字母結尾的最長回文子串的長度,也就是說dp[i]表示以s[i]結尾的最長回文子串的長度。
  • 單序列與雙序列動態規劃經典題解
    reference: nine chapter algrithm本篇給出一道單序列動態規劃題解的詳細分析過程,再給一道雙序列型動態規劃
  • LeetCode 例題精講 | 04 用雙指針解 Two Sum:縮減搜索空間
    但事實上,這個解法並不是能讓人一眼就看懂。我第一次看到這道題的答案時,把這個解法叫做 Amazing O(n) 解法。搜索空間的減小過程(動圖)舉一反三:二維矩陣搜索 Two Sum II 或許太過簡單,並不需要用到搜索空間的知識。那麼讓我們來看看這個思想在另一個例題中的應用。