2019獨角獸企業(yè)重金招聘Python工程師標(biāo)準(zhǔn)>>>

適合動態(tài)規(guī)劃（DP，dynamic programming）方法的最優(yōu)化問題有兩個要素：最優(yōu)子結(jié)構(gòu)和重疊子問題。

最優(yōu)子結(jié)構(gòu)指的是最優(yōu)解包含的子問題的解也是最優(yōu)的。

重疊子問題指的是每次產(chǎn)生的子問題并不總是新問題，有些子問題會被重復(fù)計算多次。

所以可以用如下步驟來解決：

遞歸定義最優(yōu)解計算公式

構(gòu)造dp矩陣，按照公式逐步計算。

接下來我們分別在最長公共子串、最長公共子序列和01背包問題中演示如何應(yīng)用上面的套路。

開始討論之前要明白子串和子序列的區(qū)別在于：子串要求在原字符串中是連續(xù)的，而子序列則沒有要求[1]。例如， 字符串 s1=abcde，s2=ade，則LCStr=de，LCSeq=ade。

其中LCStr表示Longest Common Substring 。LCSeq表示Longest Common Subsequence。

1 最長公共子串

問題定義

對于兩個字符串，請設(shè)計一個時間復(fù)雜度為O(m*n)的算法(這里的m和n為兩串的長度)，求出兩串的最長公共子串的長度。 給定兩個字符串A和B，同時給定兩串的長度n和m。

測試樣例："1AB2345CD",9,"12345EF",7

返回：4

1.1 遞歸公式

假設(shè)有字符串x，y

f(i,j)表示x中以x[i]結(jié)尾的子串集合和y中以y[j]結(jié)尾的子串集合，兩者交集中最長串的長度。（i和j都在合法范圍內(nèi)）

比如x="caba"，以a[2]結(jié)尾的子串集合如下： { "b","ab","cab"}

當(dāng)x[i]!=y[j]時，毫無疑問，交集為空集，此時f(i,j) = 0

當(dāng)x[i]==y[j]時，f(i,j) = f(i-1,j-1) + 1

當(dāng)i=0或者j=0時，f(i,j) = 0 //遞歸出口，邊界情況

1.2 dp矩陣

有了遞歸公式就可以設(shè)計dp表格了，假設(shè)x="caba" , y="bab" , 二維數(shù)組dp[i][j]對應(yīng)f(i,j)。當(dāng)x[i]==y[j]時，dp[i][j]=dp[i-1][j-1]+1

從左到右，從上到下計算得到dp表格：

同樣的本題的dp表格如下

1.3 AC代碼

class LongestSubstring { public:int findLongest(string A, int n, string B, int m) {//初始化n*m matrixvector<vector<int> > dp(n,vector<int>(m,0));int res=0;for(int i=0;i<n;i++)//x串{for(int j=0;j<m;j++)// y串{if(A.at(i)==B.at(j)){if(i==0||j==0) dp[i][j]=1;else dp[i][j]=dp[i-1][j-1]+1;// udpate maximumif(res<dp[i][j]) res=dp[i][j];}}}return res;} };

2 最長公共子序列LCS

問題定義

對于兩個字符串，請設(shè)計一個高效算法，求他們的最長公共子序列的長度， 這里的最長公共子序列定義為：有字符串A的下標(biāo)序列U1,U2,U3...Un和字符串B的下標(biāo)序列V1,V2,V3...Vn,其中Ui < Ui+1，Vi < Vi+1。且A[Ui] == B[Vi]。

給定兩個字符串A和B，同時給定兩個串的長度n和m，請返回最長公共子序列的長度。保證兩串長度均小于等于300。

測試樣例："1A2C3D4B56",10,"B1D23CA45B6A",12

返回：6

2.1 遞歸公式

假設(shè)有字符串x和y， 這里我們用x[0,i]來表示x中下標(biāo)為[0,i]的子串切片，對應(yīng)于python中的x[0:i+1]。比如x="abcdea"，那么x[0,1]就表示"ab"。

定義f(i,j)表示x[0,i]和y[0,j]之間的最長公共子序列。

毫無疑問我們又要想辦法用f(i-1,j-1)來表示f(i,j)。

當(dāng)x[i]==y[j]時，f(i,j) = f(i-1,j-1) +1

當(dāng)x[i]!=y[j]時，f(i,j) = max( f(i-1,j) , f(i,j-1) )

同樣的為保證f()參數(shù)合法，當(dāng)參數(shù)小于0時，返回值為0。

當(dāng)i<0或者j<0時，f(i,j)=0 //遞歸出口

這不難理解，比如f(0,0)實際上比較的是x[0]和y[0]兩個字符的最長公共子序列，無非是0或者1。

而f(-1,2)中參數(shù)-1表示x取一個空串，y取y[0,2]。空串和任何字符串的LCS毫無疑問都是0

2.2 dp矩陣

以x="abcdea"，y="aebcda"為例，構(gòu)造dp表格如下：

2.3 AC代碼

class LCS { public:int findLCS(string A, int n, string B, int m) {vector<vector<int> > dp(n,vector<int>(m,0));for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(A[i]==B[j]){ int t=0;if(i-1>=0 && j-1>=0) t=dp[i-1][j-1];dp[i][j]=t+1;} else{ int t1=0;int t2=0;if(i-1>=0) t1=dp[i-1][j];if(j-1>=0) t2=dp[i][j-1];dp[i][j]=max(t1,t2);}}}//右下角return dp[n-1][m-1];} };

這里需要考慮的邊界情況較多，為簡化代碼，可以考慮字符串從1開始數(shù)

dp[i][j]就表示x[0,i-1]和y[0,j-1]的最長公共子序列

對應(yīng)遞歸公式[1]：

這樣的dp矩陣，字符串的下標(biāo)和矩陣的行號列號會有些錯位：

不需要判斷越界問題，代碼精簡，但是不好理解

class LCS { public:int findLCS(string A, int n, string B, int m) {//(n+1)*(m+1)vector<vector<int> > dp(n+1,vector<int>(m+1,0)); //按照dp的index來填充矩陣for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){ if(A[i-1]==B[j-1]) dp[i][j]=dp[i-1][j-1]+1;else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}return dp[n][m];} };//或者class LCS { public:int findLCS(string A, int n, string B, int m) {vector<vector<int> > dp(n+1,vector<int>(m+1,0)); //按照string的索引來填充dp矩陣for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(A[i]==B[j]) dp[i+1][j+1]=dp[i][j]+1;else dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);}}return dp[n][m];} };

3 01背包問題

問題定義[2]

話說有一哥們?nèi)ド掷锿姘l(fā)現(xiàn)了一堆寶石，他數(shù)了數(shù)，一共有n個。 但他身上能裝寶石的就只有一個背包，背包的容量為C。這哥們把n個寶石排成一排并編上號： 0,1,2,…,n-1。第i個寶石對應(yīng)的價值和重量分別為V[i]和W[i] 。排好后這哥們開始思考： 背包總共也就只能裝下體積為C的東西，那我要裝下哪些寶石才能讓我獲得最大的利益呢？

背包問題分為01背包問題和部分背包問題，區(qū)別在于物品是否不可分割。

這里的物品不能分割，討論的是01背包問題。

假設(shè)有1,2,3...n一共n個物品。其中v[i]表示第i個物品價值。w[i]表示第i個物品重量。

d(i,j)表示，要把前i個物品放入背包，背包容量為j

• 1 遞歸公式：d(i,j)=

  • 0 //i is 0
  • max( d(i-1,j) , d(i-1,j-w[i])+v[i] ) //j>=w[i] and i>0

• 2 列表計算

占位

#include<iostream> #include <stdio.h> #include<vector> //#include"fsjtools.h" using namespace std; int main() {int n,c;//number,capwhile(cin>>n>>c){vector<int> w(n+1,0);//weightvector<int> v(n+1,0);//valuefor(int i=1;i<=n;i++) cin>>w[i]>>v[i];//start from 1//printVector(w);//printVector(v);vector<vector<int> > dp(n+1,vector<int>(c+1,0));//初始化為0for(int i=1;i<=n;i++){for(int j=0;j<=c;j++){if(j>=w[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]] + v[i]);else dp[i][j]=dp[i-1][j];}}cout<<dp[n][c]<<endl;} } 樣例輸入5 10 4 9 3 6 5 1 2 4 5 14 9 4 20 3 6 4 20 2 45 10 2 6 2 3 6 5 5 4 4 6樣例輸出19 40 15

References

DP：LCS（最長公共子串、最長公共子序列）

動態(tài)規(guī)劃之背包問題（一）

轉(zhuǎn)載于:https://my.oschina.net/SnifferApache/blog/754122

總結(jié)

以上是生活随笔為你收集整理的动态规划套路在最长公共子串、最长公共子序列和01背包问题中的应用的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。