演算法·流年（1）徹底弄懂動態規劃(Dynamic Programming)：一個問題和一百個角度

第零節開篇

前幾天，我發出了從譜定理（Spectral Theorem）講起的「Linear系列「的第一篇文章《Linear.1 譜定理（Spectral Theorem ）通往PCA和SVD的基石》，今天我準備為另外一個平行系列起頭，這個系列叫「演算法·流年」。如果說，我的真正數學啟蒙是後大學時代才開始的，那麼當我開始思考（回顧）演算法的時候，我彷彿看見了我的大學時代就在眼前。那麼真切地，我彷彿聽到了流年的聲音，我真的很懷念。如今我依然停留在原地，而你們早已走遠了。

「成長是一扇樹葉的門，童年有一群親愛的人，春天是一段路程，滄海桑田的擁有。」

Hi，很高興見到你，「演算法，流年」。

是以為開篇。

第一節問題描述

我覺得學習演算法的一個好習慣，是在恰當的時候，選擇一個非常典型的用該演算法解決的難度中等的問題，將其徹底學透。徹底學透的含義是，不能滿足於我大概理解了，或者我可以把演算法用代碼實現出來了，而是真正做到「橫看成嶺側成峰，遠近高低各不同」，要去用「一百個角度」仔細觀察其「廬山真面目」。這也是做學問的人應該秉持的做學問的態度。

我這裡選取的動態規劃

（Dynamic Programming）問題，也是LeetCode上的第十題「Regular Expression Matching」（鏈接：https://leetcode.com/problems/regular-expression-matching/）。這道題是一道關於正則表達式匹配的問題，具體描述如下：

給定一個字元串（s）和一個正則表達式（p），判斷字元串和正則表達式是否匹配。在本問題中，正則表達式僅僅支持『.』和『*』這兩種符號。
Note：i.『.』匹配任意單一字母。ii.『*』匹配0次或者多次『*』之前的那個字母。iii. 字元串s可以為空，只包含a-z的字母。iv. 正則表達式p可以為空，只包含a-z以及符號『.』和『*』。Examples1：

輸入：
s = "aa"p = "a"輸出：falseExample 2：輸入：s = "aa"p = "a*"輸出：true解釋：「a*」表示匹配0次或者多次『a』，如果匹配兩次『a』，我們就得到了「aa」。

Example 3：
輸入：s = "ab"p = ".*"輸出：true解釋：".*"表示匹配0次或者多次『.』，也就是匹配0次或者多次任意字母的意思，所以可以匹配一次『a』再匹配一次『b』，我們就得到了「ab」。Example 4：輸入：s = "aab"p ="c*a*b"

輸出: true
解釋：「c*」匹配0次『c』，「a*」匹配兩次『a』，『b』匹配『b』，我們就得到了「aab」。

第二節「從左往右看」的動態規劃

動態規劃演算法的關鍵是我們需要寫出「狀態轉移方程」，使得原狀態可以利用子狀態來表示。而這裡最最最關鍵的事情是「定義狀態」，很多時候，只要我們定義好了狀態，狀態轉移方程就是水到渠成的事情。那麼怎麼定義狀態呢，這得有賴於我們的「嗅覺」，或者就說是靈感吧。靈感來源於哪呢？我覺得來源於把經典問題鑽研透徹的過程，比如我就特別建議大家跟著我把這個正則表達式匹配的問題搞清楚。

本文研究的狀態轉移方程，會考慮適配C語言的語法規範，這樣方便於用C語言實現我們的演算法。

假設字元串s的長度為len1，那麼字元串的下標是0,...,len1-1，並且s[len1] 為『』。

同理正則表達式p的長度為len2，那麼其下標是0,...,len2-1，並且p[len2]為『』。

dp[i][j]，代表一個「狀態」，它的含義是s下標小於i的部分和p下標小於j的部分的匹配狀況，如果匹配，那麼dp[i][j]為1，反之，dp[i][j]為0。在這個狀態定義下，dp[i][j]是dp[m][n]的子狀態，當且僅當。（似乎我們是在從左往右看）

且看以上的狀態定義里的加粗的「小於」，為什麼是「小於」而不是「小於等於」呢？

其實「小於等於」從理論上來說也是可以的，但是為了方便C語言的實現，「小於等於」就不合適了。原因在於，在C語言里數組的合法下標是從0開始的，如果是「小於等於」，那麼dp[0][0]的含義就變成了字元串「s[0]」和正則表達式「p[0]」的匹配狀況，這樣的話對於更「小」的空字元串就無法表示了。事實上，我們希望dp[0][0]表示空字元串和空正則表達式的匹配狀況，而dp[1][1]來表示s下標小於1的部分和p下標小於1的部分的匹配狀況，也就是字元串「s[0]」和正則表達式「p[0]」的匹配狀況。也就是定義成「小於」，就是方便我們用適配C語言的方式（數組下標大於等於0），讓dp[i][j]可以描述任意子狀態。

狀態定義好了，這個問題的狀態轉移方程也就呼之欲出了。研究狀態轉移方程就是我們在自己心裡問自己這樣一個問題，怎麼用dp[i][j]的子狀態去描述dp[i][j]。

dp[i][j]描述了s下標小於i的部分和p下標小於j的部分的匹配狀況。

如果p[j-1]不是『*』。

if(p[j-1] != *) dp[i][j] = (s[i-1] == p[j-1] || p[j-1] == .) && dp[i-1][j-1];

以上代碼用大白話說，dp[i][j]要匹配的話，那麼最後尾端的那個字元（s[i-1] != p[j-1] || p[j-1] == .）要匹配並且前面所有的東西（dp[i-1][j-1]）要匹配。

如果p[j-1]是*。

if(p[j-1] == *) dp[i][j] = dp[i][j-2] || ((s[i-1] == p[j-2] || p[j-2] == .) && dp[i-1][j]);

以上代碼用大白話說，dp[i][j]要匹配的話，要麼乾脆「p[j-2]*」不參與匹配並且前面所有的東西（dp[i][j-2]）要匹配，要麼「p[j-2]*」匹配掉了s[i-1]並且前面所有的東西（dp[i-1][j]）要匹配。

到這裡這個問題的核心已經解決了。現在，要把初始狀態設置好。

dp[0][0] = 1;

for(i = 1; i <= len1; i++)
dp[i][0] = 0;

for(j = 1; j <= len2; j++) {
if(j%2 == 0)
dp[0][j] = dp[0][j-2] && (p[j-1] == *);
else
dp[0][j] = 0;
}

dp[0][0] = 1 表示「空字元串」和「空正則表達式」匹配。
第一個for循環表示「非空子字元串」均不和「空正則表達式」匹配。第二個for循環表示「空字元串」在特殊條件下可以和「非空正則表達式」匹配，例如「」和「a*b*c*d*」匹配。

當我們定義好狀態，找到狀態轉移方程，並設置好「初始狀態」，我們的動態規劃程序已經完成了。

能夠被LeetCode 「10.Regular Expression Matching」接受的代碼版本1：

int isMatch(char * s, char * p){ int len1, len2, i, j;

//int **dp;
int dp[30][30];

len1 = strlen(s);
len2 = strlen(p);

/*
dp = (int **)malloc((len1+1)*sizeof(int*));
for(i = 0; i <= len1; i++) {
dp[i] = (int *)malloc((len2+1)*sizeof(int));
}
*/

dp[0][0] = 1;

for(i = 1; i <= len1; i++)
dp[i][0] = 0;

for(j = 1; j <= len2; j++) {
if(j%2 == 0)
dp[0][j] = dp[0][j-2] && (p[j-1] == *);
else
dp[0][j] = 0;
}

for(i = 1; i <= len1; i++)
for(j = 1; j <= len2; j++) {
if(p[j-1] != *) {
/*
if(s[i-1] == p[j-1] || p[j-1] == .)
dp[i][j] = dp[i-1][j-1];
else
dp[i][j] = 0;
*/
dp[i][j] = (s[i-1] == p[j-1] || p[j-1] == .) && dp[i-1][j-1];
}
else {
//dp[i][j] = dp[i][j-2] || ((s[i-1]==p[j-2] || p[j-2]==.) && dp[i-1][j-2]) || ((s[i-1]==p[j-2] || p[j-2]==.) && dp[i-1][j]);
dp[i][j] = dp[i][j-2] || ((s[i-1] == p[j-2] || p[j-2] == .) && dp[i-1][j]);
}
}
return dp[len1][len2];
}

以上代碼中包含了很多注釋塊。這些注釋塊可以被激活，用來替代當前程序里的被執行程序段。下面分點逐步說明。
1. 我們聲明int dp[30][30]其實是做了簡化處理，原因在於我們已經發現了LeetCode測試集的規模會小於它。而更加一般的做法是申請動態數組int **dp。這裡做一個約定，在之後沒有特殊需要的情況下，我們使用dp[30][30]。2. 「dp[i][j]=(s[i-1]== p[j-1]|| p[j-1]==.)&& dp[i-1][j-1];」這句話可以用等價的「if...else...」來表述。3. 這一點就很有意思了，「dp[i][j]= dp[i][j-2]||((s[i-1]== p[j-2]|| p[j-2]==.)&& dp[i-1][j]);」也可以寫成「dp[i][j] = dp[i][j-2] || ((s[i-1]==p[j-2] || p[j-2]==.) && dp[i-1][j-2]) || ((s[i-1]==p[j-2] || p[j-2]==.) && dp[i-1][j]);」，大家可以仔細思考下為什麼。

「激活代碼版本1中被注釋的程序段，並注釋掉與之對應的原來被執行程序段」就得到了能夠被LeetCode 「10.Regular Expression Matching」接受的代碼版本2：

int isMatch(char * s, char * p){ int len1, len2, i, j;

int **dp;
//int dp[30][30];

len1 = strlen(s);
len2 = strlen(p);

dp = (int **)malloc((len1+1)*sizeof(int*));
for(i = 0; i <= len1; i++) {
dp[i] = (int *)malloc((len2+1)*sizeof(int));
}

dp[0][0] = 1;

for(i = 1; i <= len1; i++)
dp[i][0] = 0;

for(j = 1; j <= len2; j++) {
if(j%2 == 0)
dp[0][j] = dp[0][j-2] && (p[j-1] == *);
else
dp[0][j] = 0;
}

for(i = 1; i <= len1; i++)
for(j = 1; j <= len2; j++) {
if(p[j-1] != *) {

if(s[i-1] == p[j-1] || p[j-1] == .)
dp[i][j] = dp[i-1][j-1];
else
dp[i][j] = 0;

//dp[i][j] = (s[i-1] == p[j-1] || p[j-1] == .) && dp[i-1][j-1];
}
else {
dp[i][j] = dp[i][j-2] || ((s[i-1]==p[j-2] || p[j-2]==.) && dp[i-1][j-2]) || ((s[i-1]==p[j-2] || p[j-2]==.) && dp[i-1][j]);
//dp[i][j] = dp[i][j-2] || ((s[i-1] == p[j-2] || p[j-2] == .) && dp[i-1][j]);
}
}
return dp[len1][len2];
}

代碼版本1,2都是採用「自下而上」的dp模式，我們可以將其修改成「自上而下」的dp模式。將「自下而上」的代碼版本1，修改成「自上而下」，我們就得到了能夠被LeetCode 「10.Regular Expression Matching」接受的代碼版本3：

int Dp(int i, int j, char * s, char * p, int dp[][30]) { if(dp[i][j] != -1) return dp[i][j];

if(p[j-1] != *)
dp[i][j] = (s[i-1] == p[j-1] || p[j-1] == .) && Dp(i-1, j-1, s, p,dp);
else
dp[i][j] = Dp(i, j-2, s, p, dp) || ((s[i-1] == p[j-2] || p[j-2] == .) && Dp(i-1, j, s, p, dp));

return dp[i][j];
}

int isMatch(char * s, char * p){
int len1, len2, i, j;
int dp[30][30];

len1 = strlen(s);
len2 = strlen(p);

for(i = 0; i <= len1; i++)
for(j = 0; j <= len2; j++)
dp[i][j] = -1;

dp[0][0] = 1;

for(i = 1; i <= len1; i++)
dp[i][0] = 0;

for(j = 1; j <= len2; j++) {
if(j%2 == 0)
dp[0][j] = dp[0][j-2] && p[j-1] == *;
else
dp[0][j] = 0;
}

return Dp(len1, len2, s, p, dp);
}

在版本3里，用Dp函數遞歸地搜索子狀態空間，且把計算過的子狀態存入數組dp中。dp[i][j]最開始被設為-1，用來表示此狀態沒有被計算過。之後我們用和版本1中一樣的方式來設置「初始狀態」，初始狀態對應的dp數組中的值不為-1，表示這些狀態已經被計算。當我們每次進入Dp函數，在進行當前子狀態的計算之前，我們會首先利用dp數組來判斷當前子狀態是否已被計算。如果當前子狀態對應的dp數組值不為-1，則表明當前子狀態已經被計算，我們直接返回dp數組中被記錄的值，不進行重複計算。如果當前子狀態對應的dp數組值為-1，則表明當前子狀態還沒有被計算，則遞歸地去計算當前子狀態，並將計算得到的結果保存在dp數組中，這樣，當我們下次再次搜索到當前子狀態時，就無需重複計算，直接撈取存儲在dp數組中的值就行。

版本1和版本3核心部分（狀態轉移方程）的寫法，可以形成對照。

版本1核心部分：

for(i = 1; i <= len1; i++) for(j = 1; j <= len2; j++) { if(p[j-1] != *) dp[i][j] = (s[i-1] == p[j-1] || p[j-1] == .) && dp[i-1][j-1]; else dp[i][j] = dp[i][j-2] || ((s[i-1] == p[j-2] || p[j-2] == .) && dp[i-1][j]); }

版本3核心部分：

int Dp(int i, int j, char * s, char * p, int dp[][30]) { if(dp[i][j] != -1) return dp[i][j];

if(p[j-1] != *)
dp[i][j] = (s[i-1] == p[j-1] || p[j-1] == .) && Dp(i-1, j-1, s, p,dp);
else
dp[i][j] = Dp(i, j-2, s, p, dp) || ((s[i-1] == p[j-2] || p[j-2] == .) && Dp(i-1, j, s, p, dp));

return dp[i][j];
}

第三節「從右往左看」的動態規劃

在第二節中我們已經給出了三個代碼版本。但是這三個代碼版本沒有本質上的區別，原因在於，它們的「狀態」定義方式是一樣的。那麼除了如第二節的這種狀態定義方式，我們有沒有別的狀態定義方式？如果說，第二節的狀態定義方式，我們是在「從左往右看」，而如今我們不妨試試「從右往左看」。

dp[i][j]，代表一個「狀態」，它的含義是s下標大於等於i的部分和p下標大於等於j的部分的匹配狀況，如果匹配，那麼dp[i][j]為1，反之，dp[i][j]為0。在這個狀態定義下，dp[i][j]是dp[m][n]的子狀態，當且僅當。（似乎我們是在從右往左看）

這一節的內容可以和第二節的內容形成嚴格對照（思路上來說是一模一樣的）。所以接下來的內容，我都是以提問的形式來寫，希望讀者朋友可以自己來回答。

為什麼狀態定義里用了「大於等於」？（理由和第二節里用「小於」是對照的）

狀態轉移方程怎麼寫？（對比第二節里狀態轉移方程的寫法）

怎麼設置初始狀態？（對比第二節里初始狀態的設置方法）

當我們定義好狀態，找到狀態轉移方程，並設置好「初始狀態」，我們的動態規劃程序已經完成了。

能夠被LeetCode 「10.Regular Expression Matching」接受的代碼版本4：

int isMatch(char * s, char * p) { int i, j, len1, len2;

int dp[30][30];

len1 = strlen(s);
len2 = strlen(p);

dp[len1][len2] = 1;

for(i = len1-1; i >= 0; i--)
dp[i][len2] = 0;

for(j = len2-1; j >= 0; j--) {
if((len2 - j) % 2 == 0)
dp[len1][j] = dp[len1][j+2] && p[j+1] == *;
else
dp[len1][j] = 0;
}

for(i = len1-1; i >= 0; i--)
for(j = len2-1; j >= 0; j--) {
if(p[j+1] != *)
dp[i][j] = (s[i] == p[j] || p[j] == .) && dp[i+1][j+1];
else
dp[i][j] = dp[i][j+2] || ((s[i] == p[j] || p[j] == .) && dp[i+1][j]);
}

return dp[0][0];
}

「代碼版本4」和「代碼版本1」形成嚴格對照，讀者朋友也可以從「代碼版本4」本體中找到我前面期待讀者朋友思考的問題的答案。

在第二節里，我們已經知道「自下而上」的版本1可以改寫成「自上而下」的版本3。同理，「自下而上」的版本4也可以擁有「自上而下」的改編版本，因為採用的方式實屬與第二節里講述的東西完全類似，這裡就請讀者朋友們自己嘗試著改編（作業！！敲黑板！！）。

第四節動態規劃？遞歸？

第三節里的狀態定義方式和第二節里的狀態定義方式，是完全不同的，但是從廣義上來說，它們也屬於一類的方法。下面，我想開始說一個切入角度很不一樣的新方法。

這個演算法思路是這樣的，對於當前的s，p，我們將其當做一個狀態。下面，我們開始尋找子狀態。我們首先檢查正則表達式p，並將其中第一個『*』的下標記為j。這裡有兩種情況：

第一種情況是正則表達式p裡面不含『*』，這時這個問題已經是一個trivial的問題了，我們直接判斷s和不含『*』的p是否匹配。

第二種情況是正則表達式p裡面含有『*』，且我們把第一個*的下標記為j。在這種情況下，我們首先比對s，p下標為0,...,j-2的部分，也就是完全不受『*』影響的部分，我們可以用一個函數check(s, p, j-2)來描述。

如果check(s, p, j-2) 為 0，表示s，p下標為0,...,j-2這個不含『*』的部分並不匹配，這也就意味著s和p並不匹配。

如果check(s, p, j-2)為1，表示s，p下標為0,...,j-2這個不含『*』的部分匹配。這時我們可以分別考慮「p[j-1]*」匹配0次，匹配1次，匹配2次，匹配3次...

如果把當前狀態記為find(s, p)，函數值為1表示匹配，0表示不匹配，那麼狀態轉移方程如下：

find(s, p) = check(s, p, j-2) &&

(
find(s+j-1, p+j+1) ||(some conditions && find(s+j, p+j+1)) ||(some conditions && find(s+j+1, p+j+1)) ||(some conditions && find(s+j+2, p+j+1)) ||...)

其中，

j是數組p中第一個『*』的下標，

find(s+j-1, p+j+1) 表示「p[j-1]*」匹配0次，

(some conditions && find(s+j, p+j+1))表示「p[j-1]*」匹配1次，

(some conditions && find(s+j+1, p+j+1))表示「p[j-1]*」匹配2次，

(some conditions && find(s+j+2, p+j+1))表示「p[j-1]*」匹配3次。

對比第二節第三節動態規劃的狀態轉移方程，本節提出的方法里的狀態轉移方程里最特殊的一點是check(s, p, j-2)這一項，正因為這一項的存在，導致「自下而上」的實現方法需要打上一個問號，因為我們要處理find(s, p)這個問題，一定要首先計算j，在check(s, p, j-2)之後，我們才可以知道find(s, p)依賴的子狀態是哪些，所以從本節方法的狀態轉移方程來看，它天生擁有「自上而下」的特性。

從本質上看，本節描述的這種方法也擁有「原狀態可以利用子狀態來表示」的特徵，它也擁有類似於狀態轉移方程的東西（只是其中有比較特殊的項check(s, p, j-2)），所以從廣義上來說，這應該也算是動態規劃的演算法，但是就如前面所說，本節方法自帶「自上而下」的特性（「自上而下」地遞歸地搜索子狀態空間），所以本方法更準確的叫法，應該是遞歸。

【說明：動態規劃一般有「自下而上」和「自上而下」（遞歸）兩種寫法，而本節描述的方法只能寫成「自上而下」（遞歸）的形式，因此就把它叫遞歸吧】

我們從「自上而下」的版本3里知道，在遞歸時會記錄子狀態從而避免重複計算，本方法在實現時依然會使用類似的技巧。

能夠被LeetCode 「10.Regular Expression Matching」接受的代碼版本5：

int check(char * s, char * p, int idx) { int i;

for(i = 0; i <= idx; i++) {
if(s[i] == p[i] || p[i] == .) {}
else { return 0;}
}

return 1;
}

int find(char * s, char * p, int ** r){
int len1, len2, i, j, flag;

len1 = strlen(s);
len2 = strlen(p);

if(r[i][j] != -1)
return r[i][j];

flag = 0;

for(j = 0; j < len2; j++)
if(p[j] == *) {
flag = 1;
break;
}

if(!flag) {
if(len1 == len2)
r[len1][len2] = check(s, p, len1-1);
else
r[len1][len2] = 0;

return r[len1][len2];
}

if(j-2 > len1-1) {
r[len1][len2] = 0;
return r[len1][len2];
}

if(check(s, p, j-2)) {
if(find(s+j-1, p+j+1, r)) {
r[len1][len2] = 1;
return r[len1][len2];
}
else {
i = j - 1;
while(i <= len1-1) {
if(s[i] == p[j-1] || p[j-1] == .) {
if(find(s+i+1, p+j+1, r)) {
r[len1][len2] = 1;
return r[len1][len2];
}
}
else{
r[len1][len2] = 0;
return r[len1][len2];
}
i++;
}
r[len1][len2] = 0;
return r[len1][len2];
}
}
else {
r[len1][len2] = 0;
return r[len1][len2];
}
}