之前的文章 動態(tài)規(guī)劃詳解 收到了普遍的好評，今天寫一個動態(tài)規(guī)劃的經(jīng)典應(yīng)用：正則表達式。如果有讀者對「動態(tài)規(guī)劃」還不了解，建議先看一下上面那篇文章。

正則表達式匹配是一個很精妙的算法，而且難度也不小。本文主要寫兩個正則符號的算法實現(xiàn)：點號「.」和星號「*」，如果你用過正則表達式，應(yīng)該明白他們的用法，不明白也沒關(guān)系，等會會介紹。文章的最后，還會介紹一種快速看出重疊子問題的技巧。

本文還有一個重要目的，就是教會讀者如何設(shè)計算法。我們平時看別人的解法，直接看到一個面面俱到的完整答案，總覺得無法理解，以至覺得問題太難，自己太菜。我力求向讀者展示，算法的設(shè)計是一個螺旋上升、逐步求精的過程，絕不是一步到位就能寫出正確算法的。本文會帶你解決這個較為復(fù)雜的問題，讓你明白如何化繁為簡，逐個擊破，從最簡單的框架搭建出最終的答案。

前文無數(shù)次強調(diào)的框架思維，就是在這種設(shè)計過程中逐步培養(yǎng)的。下面進入正題，首先看一下題目：

一、熱身

第一步，我們暫時不管正則符號，如果是兩個普通的字符串進行比較，如何進行匹配？我想這個算法應(yīng)該誰都會寫：

然后，我稍微改造一下上面的代碼，略微復(fù)雜了一點，但意思還是一樣的，很容易理解吧：

如上改寫，便于理解如何將這個算法改造成遞歸算法（偽碼）：

如果你能夠理解這段代碼，恭喜你，你的遞歸思想已經(jīng)到位，而且正則表達式問題已經(jīng)解決了一半。

二、處理點號「.」通配符

點號可以匹配任意一個字符，萬金油嘛，其實是最簡單的。將上述偽碼改成 python 代碼，再稍加改造即可：

三、處理星號「*」通配符

星號通配符可以讓前一個字符出現(xiàn)任意次數(shù)，包括零次。那到底是出現(xiàn)幾次呢？這似乎有點困難，不過不要著急，我們起碼可以把框架的搭建再進一步：

星號前面的那個字符到底要出現(xiàn)幾次呢？這需要計算機暴力窮舉的，假設(shè)出現(xiàn) N 次吧。前文多次強調(diào)過，寫遞歸的技巧是管好當下，之后的事拋給遞歸。具體到這里，不管 N 是多少，當前的選擇只有兩個：出現(xiàn) 0 次、出現(xiàn) 1 次。所以可以這樣處理：

配合一個圖示就能理解這個邏輯了。假設(shè) pattern = 'a*', text = 'aa'，畫個圖：

可以看到，我們是通過保留 pattern 中的「*」，同時向后推移 text，來實現(xiàn)「*」讓字符出現(xiàn)多次的功能。

至此，正則表達式算法就完成了，這個問題根本沒有看起來那么困難，對吧？現(xiàn)在只需要用下備忘錄或者

DP table 消除「重疊子問題」，降低一下復(fù)雜度就行了。

四、動態(tài)規(guī)劃

我選擇使用「備忘錄」遞歸的方法來降低復(fù)雜度。有了暴力解法，優(yōu)化的過程及其簡單，就是使用兩個變量 i, j 記錄當前匹配到的位置，從而避免使用子字符串切片，并且將 i, j 存入備忘錄，避免重復(fù)計算即可。

我將暴力解法和優(yōu)化解法放在一起，方便你對比，你可以發(fā)現(xiàn)優(yōu)化解法無非就是把暴力解法「翻譯」了一遍，加了個 memo 作為備忘錄，僅此而已。

有的讀者也許會問，你怎么知道這個問題是個動態(tài)規(guī)劃問題呢，你怎么知道它就存在「重疊子問題」呢？這似乎不容易看出來呀。

解答這個問題，最直觀的應(yīng)該是隨便假設(shè)一個輸入，然后畫遞歸樹，肯定是可以發(fā)現(xiàn)相同節(jié)點的。這屬于定量分析，其實不用這么麻煩，下面教你定性分析，一眼就能看出「重疊子問題」性質(zhì)。

先拿最簡單的斐波那契數(shù)列舉例，我們抽象出遞歸算法的框架：

看著這個框架，請問原問題 f(n) 如何觸達子問題 f(n - 2) ？有兩種路徑，一是 f(n) -> #1 -> #1, 二是 f(n) -> #2。前者經(jīng)過兩次遞歸，后者經(jīng)過一次遞歸而已。兩條不同的計算路徑都到達了同一個問題，這就是「重疊子問題」，而且可以肯定的是，只要你發(fā)現(xiàn)一條重復(fù)路徑，這樣的重復(fù)路徑一定存在千萬條，意味著巨量子問題重疊。

同理，對于本問題，我們依然先抽出算法框架：

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。因此，本問題一定存在重疊子問題，一定需要動態(tài)規(guī)劃的優(yōu)化技巧來處理。

五、最后總結(jié)

通過本文，你深入理解了正則表達式的兩種常用通配符的算法實現(xiàn)。其實點號「.」的實現(xiàn)及其簡單，關(guān)鍵是星號「*」的實現(xiàn)需要用到動態(tài)規(guī)劃技巧，稍微復(fù)雜些，但是也架不住我們對問題的層層拆解，逐個擊破。另外，你掌握了一種快速分析「重疊子問題」性質(zhì)的技巧，可以快速判斷一個問題是否可以使用動態(tài)規(guī)劃套路解決。

回顧整個解題過程，你應(yīng)該能夠體會到算法設(shè)計的流程：從簡單的類似問題入手，給基本的框架逐漸組裝新的邏輯，最終成為一個比較復(fù)雜、精巧的算法。

所以說，讀者不必畏懼一些比較復(fù)雜的算法問題，稍加思考和類比，很多看似高大上的算法在你眼里也不過一個脆皮，不堪一擊。