這些問題大多在 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。
輸入：text1 = "abcde", text2 = "ace" 輸出：3 解釋：最長公共子序列是 "ace"，它的長度為 3。輸入：text1 = "abc", text2 = "abc"輸出：3解釋：最長公共子序列是 "abc"，它的長度為 3。輸入：text1 = "abc", text2 = "def"輸出：0解釋：兩個字符串沒有公共子序列，返回 0。讓你求兩個字符串的最長公共子序列，這道題目可謂是教科書般的經典，很多算法書籍都把這道題當作動態規劃的思維範例進行講解。
比如大名鼎鼎的 算法導論 ！！！
因此沒做過的話，還是強烈建議去做一下。
這裡還是按之前的四個步驟來思考，當然這只是一個框架用來輔助你思考，不用特別拘泥於這四個步驟：
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 所使用的最少操作數 。
你可以對一個單詞進行如下三種操作：
輸入: word1 = "horse", word2 = "ros"輸出: 3解釋: horse -> rorse (將 'h' 替換為 'r')rorse -> rose (刪除 'r')rose -> ros (刪除 'e')輸入: 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，老樣子，四個步驟分析一遍：
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 = "aa"p = "a"輸出: false解釋: "a" 無法匹配 "aa" 整個字符串。輸入:s = "aa"p = "*"輸出: true解釋: '*' 可以匹配任意字符串。輸入:s = "cb"p = "?a"輸出: false解釋: '?' 可以匹配 'c', 但第二個 'a' 無法匹配 'b'。輸入:s = "adceb"p = "*a*b"輸出: true解釋: 第一個 '*' 可以匹配空字符串, 第二個 '*' 可以匹配字符串 "dce".輸入:s = "acdcb"p = "a*c?b"輸入: false題目給定兩個字符串，一個字符串是匹配串，除了小寫字母外，匹配串裡面還包含 * 和 ? 這兩個特殊字符，另一個是普通字符串，裡面只包含小寫字母。
題目問這個普通字符串是否和匹配字符串相匹配，匹配規則是 ? 可以匹配單個字符， * 可以匹配一個區間，也就是多個字符，當然也可以匹配 0 個字符，也就是空串。
依然是四個步驟走一遍：
可以匹配空串、以及任意多個字符
當 * 匹配空串時：問題拆解成看子問題 pattern(0…m-1) 和 str(0…n) 是否匹配
當 * 匹配任意字符時：問題拆解成看子問題 pattern(0…m) 和 str(0…n-1) 是否匹配
`` 這裡解釋一下，匹配任意多個字符意味著之前的子問題也可以使用當前的 ，也就是用 pattern(m) 來進行匹配，因此，當前問題可以拆解成子問題 pattern(0…m) 和 str(0…n-1) 是否匹配，你發現弄來弄去，子問題依然是那三個：
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 交錯組成的。
輸入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"輸出: true輸入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"輸出: false題目的輸入是三個字符串，問其中兩個字符串是否能夠交錯合併組成第三個字符串， 一個字符相對於其他字符的順序在合併之後不能改變 ，這也是這道題的難點，不然的話你用一個哈希表就可以做了，三個字符串是否意味著要開三維的狀態數組？還是四個步驟來看看：
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 難度，弄清楚了這些套路後，回過頭去看看推導過程，然後再看看二、三十行的代碼量，不知道是否能給你一些新的感悟和認識？