之前的文章 動態規劃詳解 收到了普遍的好評，今天寫一個動態規劃的經典應用：正則表達式。如果有讀者對「動態規劃」還不了解，建議先看一下上面那篇文章。
正則表達式匹配是一個很精妙的算法，而且難度也不小。本文主要寫兩個正則符號的算法實現：點號「.」和星號「*」，如果你用過正則表達式，應該明白他們的用法，不明白也沒關系，等會會介紹。文章的最后，還會介紹一種快速看出重疊子問題的技巧。
本文還有一個重要目的，就是教會讀者如何設計算法。我們平時看別人的解法，直接看到一個面面俱到的完整答案，總覺得無法理解，以至覺得問題太難，自己太菜。我力求向讀者展示，算法的設計是一個螺旋上升、逐步求精的過程，絕不是一步到位就能寫出正確算法的。本文會帶你解決這個較為復雜的問題，讓你明白如何化繁為簡，逐個擊破，從最簡單的框架搭建出最終的答案。
前文無數次強調的框架思維，就是在這種設計過程中逐步培養的。下面進入正題，首先看一下題目：
一、熱身
第一步，我們暫時不管正則符號，如果是兩個普通的字符串進行比較，如何進行匹配？我想這個算法應該誰都會寫：
然后，我稍微改造一下上面的代碼，略微復雜了一點，但意思還是一樣的，很容易理解吧：
如上改寫，便于理解如何將這個算法改造成遞歸算法（偽碼）：
如果你能夠理解這段代碼，恭喜你，你的遞歸思想已經到位，而且正則表達式問題已經解決了一半。
二、處理點號「.」通配符
點號可以匹配任意一個字符，萬金油嘛，其實是最簡單的。將上述偽碼改成 python 代碼，再稍加改造即可：
三、處理星號「*」通配符
星號通配符可以讓前一個字符出現任意次數，包括零次。那到底是出現幾次呢？這似乎有點困難，不過不要著急，我們起碼可以把框架的搭建再進一步：
星號前面的那個字符到底要出現幾次呢？這需要計算機暴力窮舉的，假設出現 N 次吧。前文多次強調過，寫遞歸的技巧是管好當下，之后的事拋給遞歸。具體到這里，不管 N 是多少，當前的選擇只有兩個：出現 0 次、出現 1 次。所以可以這樣處理：
配合一個圖示就能理解這個邏輯了。假設 pattern = 'a*', text = 'aa'，畫個圖：
可以看到，我們是通過保留 pattern 中的「*」，同時向后推移 text，來實現「*」讓字符出現多次的功能。
至此，正則表達式算法就完成了，這個問題根本沒有看起來那么困難，對吧？現在只需要用下備忘錄或者
DP table 消除「重疊子問題」，降低一下復雜度就行了。
四、動態規劃
我選擇使用「備忘錄」遞歸的方法來降低復雜度。有了暴力解法，優化的過程及其簡單，就是使用兩個變量 i, j 記錄當前匹配到的位置，從而避免使用子字符串切片，并且將 i, j 存入備忘錄，避免重復計算即可。
我將暴力解法和優化解法放在一起，方便你對比，你可以發現優化解法無非就是把暴力解法「翻譯」了一遍，加了個 memo 作為備忘錄，僅此而已。
有的讀者也許會問，你怎么知道這個問題是個動態規劃問題呢，你怎么知道它就存在「重疊子問題」呢？這似乎不容易看出來呀。
解答這個問題，最直觀的應該是隨便假設一個輸入，然后畫遞歸樹，肯定是可以發現相同節點的。這屬于定量分析，其實不用這么麻煩，下面教你定性分析，一眼就能看出「重疊子問題」性質。
先拿最簡單的斐波那契數列舉例，我們抽象出遞歸算法的框架：
看著這個框架，請問原問題 f(n) 如何觸達子問題 f(n - 2) ？有兩種路徑，一是 f(n) -> #1 -> #1, 二是 f(n) -> #2。前者經過兩次遞歸，后者經過一次遞歸而已。兩條不同的計算路徑都到達了同一個問題，這就是「重疊子問題」，而且可以肯定的是，只要你發現一條重復路徑，這樣的重復路徑一定存在千萬條，意味著巨量子問題重疊。
同理，對于本問題，我們依然先抽出算法框架：
def dp(i, j):
dp(i, j + 2) #1
dp(i + 1, j) #2
dp(i + 1, j + 1) #3
提出類似的問題，請問如何從原問題 dp(i, j) 觸達子問題 dp(i + 2, j + 2) ？至少有兩種路徑，一是 dp(i, j) -> #3 -> #3，二是 dp(i, j) -> #1 -> #2 -> #2。因此，本問題一定存在重疊子問題，一定需要動態規劃的優化技巧來處理。
五、最后總結
通過本文，你深入理解了正則表達式的兩種常用通配符的算法實現。其實點號「.」的實現及其簡單，關鍵是星號「*」的實現需要用到動態規劃技巧，稍微復雜些，但是也架不住我們對問題的層層拆解，逐個擊破。另外，你掌握了一種快速分析「重疊子問題」性質的技巧，可以快速判斷一個問題是否可以使用動態規劃套路解決。
回顧整個解題過程，你應該能夠體會到算法設計的流程：從簡單的類似問題入手，給基本的框架逐漸組裝新的邏輯，最終成為一個比較復雜、精巧的算法。
所以說，讀者不必畏懼一些比較復雜的算法問題，稍加思考和類比，很多看似高大上的算法在你眼里也不過一個脆皮，不堪一擊。
