萬字長文！動態規劃的終極難題：字元匹配類

2019 年 12 月 2 日
筆記

這些問題大多在 LeetCode 上面標的都是 hard 難度，弄清楚了這些套路後，回過頭去看看推導過程，然後再看看二、三十行的程式碼量，不知道是否能給你一些新的感悟和認識？

本文全長 1w 字，內容有點干，建議先收藏再閱讀！

概論

前面我們說了 矩陣類動態規劃 和 序列類動態規劃 這兩類動規題型，不知道你是否對動態規劃有了更多的認識。

這裡說一下，將動態規劃分不同的題型來討論主要為了更好地明確思路，往往不同類型的題目有著不同的切題點，當然你熟練了，題目做的多了，對動規思想理解透徹了，拿到一道題目馬上能想到狀態定義以及遞推方程，那其實分不分題型沒有任何差別，但是如果沒有太多基礎的，還是不太建議盲目做題，分題型來學習並總結效果可能會更好。

字元匹配類動態規劃，你一聽名字就知道和字元串匹配相關，這類題型它其實是 序列類動態規劃 的一個遞進，它有時也被稱為 雙序列類動態規劃。

在 序列類動態規劃 中，題目的輸入是一個數組或是字元串，然後讓你基於這個輸入數組或是字元串進行一系列的判斷，往往我們拆解問題、分析狀態的時候只需要考慮一個維度的狀態，比如刷房子和搶房子相關的問題，我們只需要考慮此時的房子和之前考慮過的房子之間的聯繫，思維始終是在一條線上。

回到字元匹配類動態規劃，題目要你分析的是兩個序列彼此之間的聯繫，這裡其實有一個動態規劃狀態維度的提升，在考慮當前子問題的時候，我們要同時考慮兩個序列的狀態，當然，一般說來，動態規劃狀態維度的提升，也意味著難度的提升，可能剛從一維變成二維，你會不太習慣，沒關係，多思考就好了，對於字元匹配類動態規劃，它的題目特徵其實特別明顯，比如：

輸入是兩個字元串，問是否通過一定的規則相匹配
輸入是兩個字元串，問兩個字元串是否存在包含被包含的關係
輸入是兩個字元串，問一個字元串怎樣通過一定規則轉換成另一個字元串
輸入是兩個字元串，問它們的共有部分
。。。

另外說一下，這類問題的難點在於問題的拆解上面，也就是如何找到當前問題和子問題的聯繫。

往往這類問題的狀態比較好找，你可以先假設狀態 dp[i][j] 就是子問題 str1(0...i) str2(0...j) 的狀態。拆解問題主要思考 dp[i][j] 和子問題的狀態 dp[i - 1][j]，dp[i - 1][j] 以及 dp[i - 1][j - 1] 的聯繫，因為字元串會存在空串的情況，所以動態規劃狀態數組往往會多開一格。

當然，對於這類問題，如果你還是沒有什麼思路或者想法，我給你的建議是 畫表格，我們結合實際題目一起來看看。

題目分析

LeetCode 第 1143 號問題：最長公共子序列。

題目描述

給定兩個字元串 text1 和 text2，返回這兩個字元串的最長公共子序列。

一個字元串的 子序列 是指這樣一個新的字元串：它是由原字元串在不改變字元的相對順序的情況下刪除某些字元（也可以不刪除任何字元）後組成的新字元串。例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。兩個字元串的「公共子序列」是這兩個字元串所共同擁有的子序列。

若這兩個字元串沒有公共子序列，則返回 0。

示例 1:

輸入：text1 = "abcde", text2 = "ace"  輸出：3  解釋：最長公共子序列是 "ace"，它的長度為 3。

示例 2:

輸入：text1 = "abc", text2 = "abc"  輸出：3  解釋：最長公共子序列是 "abc"，它的長度為 3。

示例 3:

輸入：text1 = "abc", text2 = "def"  輸出：0  解釋：兩個字元串沒有公共子序列，返回 0。

題目分析

讓你求兩個字元串的最長公共子序列，這道題目可謂是教科書般的經典，很多演算法書籍都把這道題當作動態規劃的思維範例進行講解。

比如大名鼎鼎的 演算法導論 ！！！

因此沒做過的話，還是強烈建議去做一下。

這裡還是按之前的四個步驟來思考，當然這只是一個框架用來輔助你思考，不用特別拘泥於這四個步驟：

問題拆解我們要求解 str1(0,…m) 和 str2(0,…n) 的最長公共子序列，如果這是最終要求解的問題，那麼它的子問題是什麼呢？其實是 str1(0,…m-1) 和 str2(0,…n-1)，以及 str1(0,…m-1) 和 str2(0,…n)，還有 str1(0,…m) 和 str2(0,…n-1)，如果要找它們之間的關係，那我們需要思考一個問題就是，這些子問題怎麼變成最終要求解的問題，當前的問題考慮當前字元是否相等，很直接的一個發現就是，如果 str1(m)==str2(n)，那麼我們就可以將子問題中的 str1(0,…m-1) 和 str2(0,…n-1) 後面添加兩個相同字元遞進成當前問題；如果不相等，我們就需要考慮在三個子問題中選擇一個較大值了。說到這裡，如果你還是不太清楚問題之間的聯繫，那我們一起來畫畫表格，熟悉一下這個過程：題目求解 text1 = "abcde", text2 = "ace" 的最長公共子序列 "" a c e "" 0 0 0 0 a 0 如果其中一個字元串是空串 b 0 那麼兩個字元不存在公共子序列 c 0 對應的子問題狀態初始化為 0 d 0 e 0 "" a c e "" 0 0 0 0 a 0 1 1 1 text1 = "a" text2 = "a" || text2 = "ac" || text2 = "ace" b 0 考慮當前狀態 dp[i][j] 的時候 c 0 我們可以考慮子狀態 dp[i – 1][j – 1] d 0 dp[i][j – 1] e 0 dp[i – 1][j] "" a c e "" 0 0 0 0 a 0 1 1 1 b 0 1 1 1 text1 = "ab" text2 = "a" || text2 = "ac" || text2 = "ace" c 0 d 0 e 0 "" a c e "" 0 0 0 0 a 0 1 1 1 b 0 1 1 1 c 0 1 2 2 text1 = "abc" text2 = "a" || text2 = "ac" || text2 = "ace" d 0 畫到這裡，不知道你有沒有發現噹噹前的字元不相同時 e 0 dp[i][j] = Math.max(dp[i – 1][j], dp[i][j – 1]) "" a c e "" 0 0 0 0 a 0 1 1 1 b 0 1 1 1 c 0 1 2 2 d 0 1 2 2 text1 = "abcd" text2 = "a" || text2 = "ac" || text2 = "ace" e 0 "" a c e "" 0 0 0 0 a 0 1 1 1 b 0 1 1 1 c 0 1 2 2 d 0 1 2 2 e 0 1 2 3 text1 = "abcde" text2 = "a" || text2 = "ac" || text2 = "ace" 3 就是我們要返回的答案
狀態定義 dp[i][j] 表示的就是 str1(0,…i) 和 str2(0,…j) 的答案，基本上字元串匹配類動態規劃都可以先嘗試這樣去定義狀態
遞推方程在拆解問題中也說了，有兩種情況，就是: 如果 str1(i) != str2(j): dp[i][j] = Math.max(dp[i – 1][j], dp[i][j – 1]) 如果 str1(i) == str2(j): dp[i][j] = Math.max(dp[i – 1][j], dp[i][j – 1], dp[i – 1][j – 1] + 1) 因為 dp[i – 1][j – 1] + 1 >= dp[i – 1][j] && dp[i – 1][j – 1] + 1 >= dp[i][j – 1] 所以第二項可以化簡：如果 str1(i) == str2(j): dp[i][j] = dp[i – 1][j – 1] + 1
實現通常來說字元相關的問題可以把狀態數組多開一格用來存放空串匹配的情況，這道題空串的情況答案都是 0，使用 Java 語言也不需要考慮初始化

參考程式碼

public int longestCommonSubsequence(String text1, String text2) {      int length1 = text1.length();      int length2 = text2.length();        int[][] dp = new int[length1 + 1][length2 + 1];        char[] textArr1 = text1.toCharArray();      char[] textArr2 = text2.toCharArray();        for (int i = 1; i <= length1; ++i) {          for (int j = 1; j <= length2; ++j) {              if (textArr1[i - 1] == textArr2[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[length1][length2];  }

LeetCode 第 72 號問題：編輯距離。

題目描述

給定兩個單詞 word1 和 word2，計算出將 word1 轉換成 word2 所使用的最少操作數。

你可以對一個單詞進行如下三種操作：

插入一個字元
刪除一個字元
替換一個字元

示例 1:

輸入: word1 = "horse", word2 = "ros"  輸出: 3  解釋:  horse -> rorse (將 'h' 替換為 'r')  rorse -> rose (刪除 'r')  rose -> ros (刪除 'e')

示例 2:

輸入: word1 = "intention", word2 = "execution"  輸出: 5  解釋:  intention -> inention (刪除 't')  inention -> enention (將 'i' 替換為 'e')  enention -> exention (將 'n' 替換為 'x')  exention -> exection (將 'n' 替換為 'c')  exection -> execution (插入 'u')

題目分析

求解編輯距離，也是經典老題，編輯距離其實在實際工作中也會用到，主要用於分析兩個單詞的相似程度，兩個單詞的編輯距離越小證明兩個單詞的相似度越高。

題目說可以通過增加字元，刪除字元，以及 替換字元 這三個操作來改變一個字元串，並且每個操作的 cost 都是 1，問一個單詞轉換成另一個單詞的最小 cost，老樣子，四個步驟分析一遍：

問題拆解我們考慮求解 str1(0…m) 通過多少 cost 變成 str2(0…n)，還是來看看它的子問題，其實還是三個
str1(0…m-1) 通過多少 cost 變成 str2(0…n)
str1(0…m) 通過多少 cost 變成 str2(0…n-1)
str1(0…m-1) 通過多少 cost 變成 str2(0…n-1) 你可能會問你怎麼這麼快就寫出子問題來，這些子問題是如何推導來的，它們和當前問題之間的聯繫又是什麼？別急，聽我慢慢道來。 一般字元匹配類問題的核心永遠是兩個字元串中的字元的比較，而且字元比較也只會有兩種結果，那就是相等和 不相等，在字元比較的結果之上我們才會進行動態規劃的統計和推導。回到這道題，當我們在比較 str1(m) 和 str2(n) 的時候也會有兩種結果，即相等或 不相等，如果說是相等，那其實我們就不需要考慮這兩個字元，問題就直接變成了子問題 str1(0…m-1) 通過多少 cost 變成 str2(0…n-1)，如果說 不相等，那我們就可以執行題目給定的三種變換策略:
將問題中的 str1 末尾字元 str1(m) 刪除，因此只需要考慮子問題 str1(0…m-1)，str2(0…n)
將問題中的 str1 末尾字元 str1(m) 替換成 str2(n)，這裡我們就只需要考慮子問題 str1(0…m-1)，str2(0…n-1)
將問題中的 str1 末尾添加一個字元 str2(n)，添加後 str1(m+1) 必定等於 str2(n)，所以，我們就只需要考慮子問題 str1(0…m)，str2(0…n-1) 如果你還不是特別清楚問題之間的關係，那就畫圖表吧，這裡我就略過。
狀態定義 dp[i][j] 表示的是子問題 str1(0…i)，str2(0…j) 的答案，和常規的字元匹配類動態規劃題目一樣，沒什麼特別
遞推方程問題拆解那裡其實說的比較清楚了，這裡需要把之前的描述寫成表達式的形式： str1(i) == str2(j): dp[i][j] = dp[i – 1][j – 1] tip: 這裡不需要考慮 dp[i – 1][j] 以及 dp[i][j – 1]，因為 dp[i – 1][j – 1] <= dp[i – 1][j] +1 && dp[i – 1][j – 1] <= dp[i][j – 1] + 1 str1(i) != str2(j): dp[i][j] = Math.min(dp[i – 1][j], dp[i][j – 1], dp[i – 1][i – 1]) + 1 你可以看到字元之間比較的結果永遠是遞推的前提
實現這裡有一個初始化，就是當一個字元串是空串的時候，轉化只能通過添加元素或是刪除元素來達成，那這裡狀態數組中存的值其實是和非空字元串的字元數量保持一致。

參考程式碼

public int minDistance(String word1, String word2) {      char[] arr1 = word1.toCharArray();      char[] arr2 = word2.toCharArray();        int[][] dp = new int[arr1.length + 1][arr2.length + 1];      dp[0][0] = 0;      for (int i = 1; i <= arr1.length; ++i) {          dp[i][0] = i;      }        for (int i = 1; i <= arr2.length; ++i) {          dp[0][i] = i;      }        for (int i = 1; i <= arr1.length; ++i) {          for (int j = 1; j <= arr2.length; ++j) {              if (arr1[i - 1] == arr2[j - 1]) {                  dp[i][j] = dp[i - 1][j - 1];              } else {                  dp[i][j] = Math.min(dp[i - 1][j],                                      Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;              }          }      }        return dp[arr1.length][arr2.length];  }

LeetCode 第 44 號問題：通配符匹配。

題目描述

給定一個字元串 (s) 和一個字元模式 (p) ，實現一個支援 '?' 和 '*' 的通配符匹配。

'?' 可以匹配任何單個字元。  '*' 可以匹配任意字元串（包括空字元串）。

兩個字元串完全匹配才算匹配成功。

說明:

s 可能為空，且只包含從 a-z 的小寫字母。
p 可能為空，且只包含從 a-z 的小寫字母，以及字元 ? 和 *。

示例 1:

輸入:  s = "aa"  p = "a"  輸出: false  解釋: "a" 無法匹配 "aa" 整個字元串。

示例 2:

輸入:  s = "aa"  p = "*"  輸出: true  解釋: '*' 可以匹配任意字元串。

示例 3:

輸入:  s = "cb"  p = "?a"  輸出: false  解釋: '?' 可以匹配 'c', 但第二個 'a' 無法匹配 'b'。

示例 4:

輸入:  s = "adceb"  p = "*a*b"  輸出: true  解釋: 第一個 '*' 可以匹配空字元串, 第二個 '*' 可以匹配字元串 "dce".

示例 5:

輸入:  s = "acdcb"  p = "a*c?b"  輸入: false

題目分析

題目給定兩個字元串，一個字元串是匹配串，除了小寫字母外，匹配串裡面還包含 * 和 ? 這兩個特殊字元，另一個是普通字元串，裡面只包含小寫字母。

題目問這個普通字元串是否和匹配字元串相匹配，匹配規則是 ? 可以匹配單個字元，* 可以匹配一個區間，也就是多個字元，當然也可以匹配 0 個字元，也就是空串。

依然是四個步驟走一遍：

問題拆解做多了，你發現這種問題其實都是一個套路，老樣子，我們還是根據我們要求解的問題去看和其直接相關的子問題，我們需要求解的問題是 pattern(0…m) 和 str(0…n) 是否匹配，這裡的核心依然是字元之間的比較，但是和之前不同的是，這個比較不僅僅是看兩個字元相不相等，它還有了一定的匹配規則在裡面，那我們就依次枚舉討論下： pattern(m) == str(n): 問題拆解成看子問題 pattern(0…m-1) 和 str(0…n-1) 是否匹配 pattern(m) == ?: 問題拆解成看子問題 pattern(0…m-1) 和 str(0…n-1) 是否匹配 `` pattern(m) == *:</li> <li>可以匹配空串、以及任意多個字元 當 * 匹配空串時：問題拆解成看子問題 pattern(0…m-1) 和 str(0…n) 是否匹配 當 * 匹配任意字元時：問題拆解成看子問題 pattern(0…m) 和 str(0…n-1) 是否匹配 ``這裡解釋一下，匹配任意多個字元意味著之前的子問題也可以使用當前的，也就是用 pattern(m) 來進行匹配，因此，當前問題可以拆解成子問題 pattern(0…m) 和 str(0…n-1) 是否匹配，你發現弄來弄去，子問題依然是那三個：
pattern(0…m-1) 和 str(0…n-1) 是否匹配
pattern(0…m-1) 和 str(0…n) 是否匹配
pattern(0…m) 和 str(0…n-1) 是否匹配不知道你是否發現了字元匹配類動態規劃問題的共性，如果是畫表格，你只需要關注當前格子的 左邊、上邊、左上 這三個位置的相鄰元素，因為表格有實際數據做輔助，所以畫表格有時可以幫助你找到問題與子問題之間的聯繫。
狀態定義還是老樣子，dp[i][j] 表示的就是問題 pattern(0…i) 和 str(0…j) 的答案，直接說就是 pattern(0…i) 和 str(0…j) 是否匹配
遞推方程把之前「問題拆解」中的文字描述轉換成狀態的表達式就是遞推方程： pattern(i) == str(j) || pattern(i) == '?': dp[i][j] = dp[i – 1][j – 1] pattern(i) == '*': dp[i][j] = dp[i – 1][j] || dp[i][j – 1]
實現這類問題的狀態數組往往需要多開一格，主要是為了考慮空串的情況，這裡我就不贅述了。我想說的是，關於初始化的部分，如果 str 是空的，pattern 最前面有 *，因為 * 是可以匹配空串的，因此這個也需要記錄一下，反過來，如果 pattern 是空的，str 只要不是空的就無法匹配，這裡就不需要特別記錄。

參考程式碼

public boolean isMatch(String s, String p) {      char[] sArr = s.toCharArray();      char[] pArr = p.toCharArray();        boolean[][] dp = new boolean[pArr.length + 1][sArr.length + 1];        dp[0][0] = true;      for (int i = 1; i <= pArr.length; ++i) {          if (pArr[i - 1] != '*') {              break;          } else {              dp[i][0] = true;          }      }        for (int i = 1; i <= pArr.length; ++i) {          for (int j = 1; j <= sArr.length; ++j) {              if (sArr[j - 1] == pArr[i - 1] || pArr[i - 1] == '?') {                  dp[i][j] = dp[i - 1][j - 1];              } else if (pArr[i - 1] == '*') {                  dp[i][j] = dp[i - 1][j] || dp[i][j - 1];              }          }      }        return dp[pArr.length][sArr.length];  }

LeetCode 第 97 號問題。

題目描述

給定三個字元串 s1, s2, s3, 驗證 s3 是否是由 s1 和 s2 交錯組成的。

示例 1:

輸入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"  輸出: true

示例 2:

輸入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"  輸出: false

題目分析

題目的輸入是三個字元串，問其中兩個字元串是否能夠交錯合併組成第三個字元串，一個字元相對於其他字元的順序在合併之後不能改變，這也是這道題的難點，不然的話你用一個哈希表就可以做了，三個字元串是否意味著要開三維的狀態數組？還是四個步驟來看看：

問題拆解在拆解問題之前，我們必須保證前兩個字元串的字元的總數量必須正好等於第三個字元串的字元總數量，不然的話，再怎麼合併也無法完全等同。這裡有一個點，當我們考慮 str1(0…i) 和 str2(0…j) 的時候，其實第三個字串需要考慮的範圍也就確定了，就是 str3(0…i+j)。如果我們要求解問題 str1(0…m) 和 str2(0…n) 是否能夠交錯組成 str3(0…m+n)，還是之前那句話，字元串匹配問題的核心永遠是字元之間的比較：
如果 str1(m) == str3(m+n)，問題拆解成考慮子問題 str1(0…m-1) 和 str2(0…n) 是否能夠交錯組成 str3(0…m+n-1)
如果 str2(n) == str3(m+n)，問題拆解成考慮子問題 str1(0…m) 和 str2(0…n-1) 是否能夠交錯組成 str3(0…m+n-1) 你可能會問需不需要考慮子問題 str1(0…m-1) 和 str2(0…n-1)？在這道題目當中，不需要！千萬不要題目做多了就固定思維了，之前說到這類問題可以試著考慮三個相鄰子問題是為了讓你有個思路，能更好地切題，並不是說所有的字元串匹配問題都需要考慮這三個子問題，我們需要遇到具體問題具體分析。
狀態定義 dp[i][j] 表示的是 str1(0…i) 和 str2(0…j) 是否可以交錯組成 str3(0…i+j)，這裡再補充說明下為什麼我們不需要開多一維狀態來表示 str3，其實很簡單，str3 的狀態是由 str1 str2 決定的，str1 str2 定了，str3 就定了
遞推方程把之前問題拆解中的文字描述轉換成狀態的表達式就是遞推方程： str1(i) == str3(i+j) dp[i][j] |= dp[i – 1][j] str2(j) == str3(i+j) dp[i][j] |= dp[i – 1][j]
實現初始化的時候需要考慮單個字元串能否組成 str3 對應的區間，這個比較簡單，直接判斷前綴是否相等即可。

參考程式碼：

public boolean isInterleave(String s1, String s2, String s3) {      int length1 = s1.length();      int length2 = s2.length();      int length3 = s3.length();        if (length1 + length2 != length3) {          return false;      }        boolean[][] dp = new boolean[length1 + 1][length2 + 1];        dp[0][0] = true;        char[] sArr1 = s1.toCharArray();      char[] sArr2 = s2.toCharArray();      char[] sArr3 = s3.toCharArray();        for (int i = 1; i <= length1; ++i) {          dp[i][0] = dp[i - 1][0] && sArr1[i - 1] == sArr3[i - 1];      }        for (int i = 1; i <= length2; ++i) {          dp[0][i] = dp[0][i - 1] && sArr2[i - 1] == sArr3[i - 1];      }        for (int i = 1; i <= length1; ++i) {          for (int j = 1; j <= length2; ++j) {              if (sArr3[i + j - 1] == sArr1[i - 1]) {                  dp[i][j] |= dp[i - 1][j];              }                if (sArr3[i + j - 1] == sArr2[j - 1]) {                  dp[i][j] |= dp[i][j - 1];              }          }      }        return dp[length1][length2];  }

總結

字元匹配類動態規劃的問題還有挺多，比如 Regular Expression、Distinct Subsequence 等等，這些問題都非常的經典，它們的難度都不低，但是這類問題其實是有套路的，首先狀態特別好找，另外拆解問題也有一定的規律。

如果還是沒有思路，那就畫畫表格吧，考慮當前格子的時候，看看其左邊，上邊，左上邊 這三個格子所代表的子問題的狀態，有實際數據作為輔助，問題之間的遞進關係相對來說會比較好找些。這些問題大多在 LeetCode 上面標的都是 hard 難度，弄清楚了這些套路後，回過頭去看看推導過程，然後再看看二、三十行的程式碼量，不知道是否能給你一些新的感悟和認識？