1. 前言

動態(tài)規(guī)劃處理字符相關(guān)案例中，求最長公共子序列以及求最短編輯距離，算是經(jīng)典中的經(jīng)典案例。

講解此類問題的算法在網(wǎng)上一抓應(yīng)用一大把，即便如此，還是忍不住有寫此文的想法。畢竟理解、看懂都不算是真正掌握，唯有瞧出其中玄機，能有自己獨有的見解和不一樣的感悟方算是把知識學到靈魂深入。

好了！閑話少說，進入正題。

2. 最長公共子序列(LCS)

2.1 問題描述

最長公共子序列，指找出 2 個或多個字符串中的最長公共子序列。

如字符串 s1=kabc和s2=taijc，其最長公共子序列是ac。

Tips： 子序列只要求其中字符保持和原字符串中一樣的順序，而不一定連續(xù)。

2.2 遞歸思想

這是一道求最值的題目，只要是求最值，必然會存在多個選擇，原理很簡單，如果沒有多個選擇，還有必要糾結(jié)誰是最大誰是最小嗎？

Tips： 在你面前有蘋果、桔子、香蕉……你只能選擇一個，這時候方有糾結(jié)。如果面前只有蘋果，還會糾結(jié)嗎？

面對此問題，可以采用化整為零的思想，從宏觀層面轉(zhuǎn)移到微觀層面，縮小問題的規(guī)模的遞歸思想。

如為字符串s1設(shè)置位置指針 i，為字符串s2設(shè)置位置指針j，則問題可以抽象為如下函數(shù)。函數(shù)的語義：i和j作為起始位置時字符串s1,s2的最長公共子序列。

int lcs(string s1,int i,string s2,int j);
//如果 s1、s2為全局變量，函數(shù)可以是
int lcs(int i,int j);  

• 初始時，i=0和j=0意味求解完整的s1和s2的最長公共子序列。此時規(guī)模最大，無法直接得到答案。如此，把問題延續(xù)到規(guī)模較小的子問題。

? 上文說過，求最值一定存在多個選擇的，原始問題中的k!=t，則可存在如下 3 種選擇：

? A、i不動，j+1。即把i指向作為起始位置的s1字符串和j+1作為起始位置的s2字符串繼續(xù)比較?？伤銥橐粋€子問題。

? B、j不動，i+1。即把i+1指向作為起始位置的s1字符串和j作為起始位置的s2字符串繼續(xù)比較?？伤銥榱硪粋€子問題。

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-Cr2f8B0w-1691975983175)(D:\紅泥巴\我的課程體系\數(shù)據(jù)結(jié)構(gòu)與算法\動態(tài)規(guī)劃系列\(zhòng)images\44.png)]

? C、i和j同時移動到下一個位置。即把i+1指向作為起始位置的s1字符串和j+1作為起始位置的s2字符串繼續(xù)比較。也算為一個子問題。

? 也就是說，當原始問題中i和j指向位置字符不相同時，存在 3 個選擇。至于子問題如何求解，這個歸功于遞歸思想。

Tips： 遞歸最大的好處就是只需要確定基礎(chǔ)函數(shù)的功能，然后確定子問題，則子問題的內(nèi)部如何求解站在宏觀角度可以不管。反之它可以一步一步繼續(xù)縮小問題規(guī)模，直到有答案為止。

? 然后在3 種選擇中，返回值最大的那一個作為當前的問題的結(jié)果。

int lcs(string s1,int i,string s2,int j){if(s1[i]!=s2[j]){//有 3 種選擇int sel_1=lcs(s1,i,s2,j+1);int sel_2=lcs(s1,i+1,s2,j);int sel_3=lcs(s1,i+1,s2,j+1);return max(sel_1,sel_2,sel_3);} 
}

• 如下圖所示，當i和j所指向位置的值相同時，必然在當前子問題中就找到了一個公共字符，則最終結(jié)果就是后續(xù)子問題的結(jié)果基礎(chǔ)上加 1 ，則為最長公共子序列為原來的值加 1。

  Tips： 在海灘上撿貝殼時，當前拾到了一個，回家時最終能拾到的貝殼一定是當前拾到的這一個加上后續(xù)所拾到的貝殼。

? 同時移動 i和j，進入規(guī)模較小的子問題。如下圖所示。

? 此時可總結(jié)一下，使用遞歸求最長公共子序列，類似于玩消消樂，相同，則消掉，直接進入剩下的內(nèi)容。不相同，選擇會多些。

int lcs(string s1,int i,string s2,int j){if(s1[i]!=s2[j]){//有 3 種選擇int sel_1=lcs(s1,i,s2,j+1);int sel_2=lcs(s1,i+1,s2,j);int sel_3=lcs(s1,i+1,s2,j+1);//三者之中選擇最大返回值}else{//只有一個選擇return lcs(s1,i+1,s2,j+1)+1;}
}

• 遞歸邊界。當i==s1.size() 或 j==s2.size()時，說明已經(jīng)掃描到了子符串的最后。如下圖所示，無論哪一個指針先到達字符串的末尾，則都不再存在任何公共子序列。

int lcs(string s1,int i,string s2,int j){if(i==s1.size() || j==s2.size())return 0;if(s1[i]!=s2[j]){//有 3 種選擇int sel_1=lcs(s1,i,s2,j+1);int sel_2=lcs(s1,i+1,s2,j);int sel_3=lcs(s1,i+1,s2,j+1);//三者之中選擇最大返回值}else{//只有一個選擇return lcs(s1,i+1,s2,j+1)+1;}
}

上述是基于遞歸的角度分析問題，完整的代碼如下：

#include <iostream>
using namespace std;
int lcs(string s1,int i,string s2,int j) {if(i==s1.size() || j==s2.size())return 0;if(s1[i]!=s2[j]) {//有 3 種選擇int sel_1=lcs(s1,i,s2,j+1);int sel_2=lcs(s1,i+1,s2,j);int sel_3=lcs(s1,i+1,s2,j+1);int maxVal=max(sel_1,sel_2);maxVal=max(maxVal,sel_3);return maxVal;} else {//只有一個選擇return lcs(s1,i+1,s2,j+1)+1;}
}
int main() {string s1,s2;cin>>s1>>s2;int res= lcs(s1,0,s2,0);cout<<res;return 0;
}

當字符串的長度較大時，基于遞歸的運算量會較大，問題在于遞歸算法中存在大量的重疊子問題。

2.3 重疊子問題

繪制遞歸樹，可清晰看到重疊子問題的存在。

并且可以看到 sel_1和sel_2分支包括sel_3分支，可以使用緩存方案解決遞歸中的重疊子問題，讓重疊子問題只被計算一次。完整代碼如下 ：

#include <iostream>
#include <map>
using namespace std;
//緩存
map<pair<int,int>,int> cache;
int lcs(string s1,int i,string s2,int j) {if(i==s1.size() || j==s2.size())return 0;pair<int,int> p= {i,j};if (cache[p] ) {return cache[p];}if(s1[i]!=s2[j]) {//有 3 種選擇int sel_1=lcs(s1,i,s2,j+1);int sel_2=lcs(s1,i+1,s2,j);cache[p]=max(sel_1,sel_2);;} else {//只有一個選擇cache[p]=lcs(s1,i+1,s2,j+1)+1;}return 	cache[p];
}
int main() {string s1,s2;cin>>s1>>s2;int res= lcs(s1,0,s2,0);cout<<res;return 0;
}

遞歸實現(xiàn)性能不可觀，代碼層面也稍顯繁瑣。類似于這樣求最值的問題，可以試著使用動態(tài)規(guī)劃來實現(xiàn)。

2.4 動態(tài)規(guī)劃

遞歸解決問題的思想是由上向下，所謂由上向下，指先擱置規(guī)模較大的問題，等規(guī)模較小的子問題解決后再回溯出大問題的解。通過上文貼的遞歸樹可以清晰看到求解流程。

動態(tài)規(guī)劃的思想是由下向上，是基于枚舉思想。記錄每一個子問題的解，最終推導(dǎo)出比之更大問題的解。當然，要求小問題具有獨立性和最優(yōu)性。

無論由上向下，還是由下向上，其本質(zhì)都是知道子問題答案后，再求解出大問題的答案。動態(tài)規(guī)劃算法是直接了當，遞歸是迂回求解。

現(xiàn)以求字符串的最長公共子序列為例，講解動態(tài)規(guī)劃的求解過程。

構(gòu)建dp數(shù)組，用來記錄所有子問題的解，類似于遞歸實現(xiàn)的緩存器。 于本問題而言，dp是一個二維數(shù)組，理論上講，從A推導(dǎo)出B，再從B推導(dǎo)出C……問題域關(guān)心的是最后的推導(dǎo)結(jié)論C，之前使用過的歷史推導(dǎo)結(jié)論其實是可以不用存儲。有點類似于"忘恩負義"，所以可以對于dp數(shù)組進行壓縮。

• 構(gòu)建dp二維數(shù)組。先初始化數(shù)組的第一行和第一列的值為0。推導(dǎo)必須有一個源頭，這里的 0就是源頭。

  當s1=""、s2="a……" 或當s1="a……"、s2=""或當s1=""、s2=""時可認為最長公共子序列的值為0。

• 如圖，讓i=1、j=1，比較 s1[i]和s2[j]位置的字符，顯然k與t是不相等的。遞歸是看后面（還沒求解）有多少個子問題可以選擇，動態(tài)規(guī)劃是看前面（已經(jīng)求解）有多個子問題會影響當前子問題。對于當前位置而言，對之有影響的位置有3個。如下圖標記為黃色區(qū)域位置。

  1位置坐標為(i,j-1)。表示s1中有k且s2中無t時最長公共子序列的值。

  2位置坐標為(i-1,j-1)。表示s1中無k且s2中無t時最長公共子序列的值。

  3位置坐標為(i-1,j)。表示s1中無k且s2中有t時最長公共子序列的值。

? 可以舍棄位置3，然后在位置1和位置2中求最大值。

• i=1不變，改成j的值。一路比較s1[i]和s2[j]中值，因都不相等，根據(jù)前面的分析，很容易填寫出dp值。

• 移動i=2，重置j=1且移動j。

  i和j所在位置的字符不相等時的問題已經(jīng)分析。

  如下圖，當 i=2,j=2時，s[i]和s[j]的值相等，則影響此位置值的前置位置應(yīng)該是哪個？

? 相等，顯然最長公共子序列會增加1，問題是在哪一個前置子問題的值上加 1？

? 其實，只需要在如下黃色區(qū)域位置的值上加上1，此位置表示當s1和s2中都沒有a的時候。

• 按如上分析原理，可以把整個dp表填寫完成。

編碼實現(xiàn)：

#include <iostream>
#include <map>
using namespace std;
int dp[100][100]= {0};
void lcs(string s1,string s2) {//初始化動態(tài)規(guī)劃表for(int i=0; i<s2.size(); i++)dp[0][i]=0;for(int i=0; i<s1.size(); i++)dp[i][0]=0;for(int i=1; i<=s1.size(); i++) {for(int j=1; j<=s2.size(); j++)if(s1[i-1]==s2[j-1]) {//相等dp[i][j]=dp[i-1][j-1]+1;} else {dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}
}
int main() {string s1,s2;cin>>s1>>s2;lcs(s1,s2);for(int i=0; i<=s1.size(); i++) {for(int j=0; j<=s2.size(); j++) {cout<<dp[i][j]<<"\t";}cout<<endl;}cout<<"最長公共子序列:"<<endl;int res=dp[s1.size()][s2.size()];cout<<res<<endl;return 0;
}

測試結(jié)果：

4. 總結(jié)

最長公共子序列很有代表性，分析基于遞歸和動態(tài)規(guī)劃的實現(xiàn)過程，可以幫助我們理解此類問題，且解決此類問題。