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

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

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

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

一、熱身

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

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

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

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

二、處理點(diǎn)號(hào)「.」通配符

點(diǎn)號(hào)可以匹配任意一個(gè)字符，萬金油嘛，其實(shí)是最簡(jiǎn)單的。將上述偽碼改成 python 代碼，再稍加改造即可：

三、處理星號(hào)「*」通配符

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

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

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

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

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

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

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

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

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

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

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

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

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

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

def dp(i, j):
 dp(i, j + 2) #1
 dp(i + 1, j) #2
 dp(i + 1, j + 1) #3

提出類似的問題，請(qǐng)問如何從原問題 dp(i, j) 觸達(dá)子問題 dp(i + 2, j + 2) ？至少有兩種路徑，一是 dp(i, j) -> #3 -> #3，二是 dp(i, j) -> #1 -> #2 -> #2。因此，本問題一定存在重疊子問題，一定需要?jiǎng)討B(tài)規(guī)劃的優(yōu)化技巧來處理。

五、最后總結(jié)

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

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

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