兩道題都是動(dòng)態(tài)規(guī)劃問題，以下內(nèi)容來自旁┮椋客網(wǎng)左神的課和書，我作為知識(shí)的搬運(yùn)工师坎，正在試圖去領(lǐng)會(huì)程序的玄妙~~
兩個(gè)題目的不同點(diǎn)是一個(gè)是子序列恕酸，不要求連續(xù)，另一個(gè)是子串胯陋，要求是連續(xù)的蕊温。
第一題：
首先生成動(dòng)態(tài)規(guī)劃表，把兩個(gè)字符串一個(gè)縱對應(yīng)遏乔，一個(gè)橫對應(yīng)寿弱，就形成了一個(gè)矩陣，這里把str1縱對應(yīng)按灶，把str2橫對應(yīng)症革。
dp[i][j]的值代表：str1[0......i]和str2[0......j]這兩個(gè)子串最長公共子序列的長度是多少。
我們在看動(dòng)態(tài)規(guī)劃問題時(shí)要先看一個(gè)重要的概念鸯旁，就是dp[i][j]的值是代表什么意義噪矛，然后再看dp[i][j]的值是怎么決策的。
首先來看動(dòng)態(tài)規(guī)劃表的第一排铺罢，假設(shè)str1長度為N艇挨，str2長度為M，那么第一排是dp[0][0......M-1]代表str1[0]和str2[0......j]的最長公共子序列韭赘。
例如對于dp[0][0],就是看str1第一個(gè)字符和str2第一個(gè)字符是否一樣缩滨，一樣的話值就為1，否則為0泉瞻。接下來dp[0][1]脉漏，if(str1[0]==str2[1])? dp[0][1]=1;?
根據(jù)dp[i][j]的含義：str1[0......i]和str2[0......j]兩個(gè)子串最長公共子序列，所以當(dāng)一行有一個(gè)位置為1袖牙，那么它后面的位置值都為1侧巨，str1[0]和str2[1]的最長公共子序列長度是1，那么str1[0]和str2[1,2],str[1,2......M-1]的最長公共子序列長度肯定都是1鞭达。同樣的道理司忱，可以得出第一列的dp值。
兩側(cè)搞定之后畴蹭，我們要看中間位置要怎么決策坦仍。dp[i][j]可能來自dp[i][j-1]，str1[0......i]和str2[0......j]的最長公共子序列長度? >= str1[0......i]和str2[0......j-1]的最長公共子序列長度叨襟。
dp[i][j]有三種來源：
①.dp[i][j-1]
②.dp[i-1][j]
③.dp[i-1][j-1]+1：當(dāng)str1[i]==str2[j]繁扎，這個(gè)字符可以作為公共序列的最后一個(gè)字符。
三種可能性選擇一個(gè)最大的作為dp[i][j]的值芹啥。
dp[i][j]:? ? ?str1[0......i]? ? ? ? ? ? ? ? str2[0......j]
dp[i][j-1]:? str1[0......i]? ? ? ? ? ? ? ? str2[0......j-1]
已經(jīng)有了動(dòng)態(tài)規(guī)劃表锻离，接下來找最長子序列：
首先找最右下角的字符，如果右下角值大于它的左邊和上邊的值墓怀，說明str1[N-1]==str2[M-1]且當(dāng)前字符是整體公共子序列的最后一個(gè)字符汽纠，這個(gè)決策時(shí)來自于左上角，當(dāng)前字符應(yīng)該被包含到最長子序列中傀履，并且向左上方移動(dòng)虱朵。
如果右下角值不比它的左邊和上邊大，此時(shí)這個(gè)字符就不應(yīng)該被包含钓账，因?yàn)檫@個(gè)決策可能來自于兩個(gè)方向碴犬，與哪邊相等就往哪邊移動(dòng)。
其實(shí)根據(jù)動(dòng)態(tài)規(guī)劃表生成結(jié)果的過程梆暮，就是利用這張表服协，來還原出整個(gè)決策路徑。
第二題：
dp[i][j]：必須以str1[i]和str2[j]結(jié)尾的條件下啦粹，str1[0......i],str2[0......j]最長公共子串是多少偿荷。
①. str1[i]！=str2[j]唠椭，那么dp[i][j]=0.
②. str1[i] ==str2[j]跳纳， 那么dp[i][j]=dp[i-1][j-1]+1.
上述方法的空間復(fù)雜度是O(M*N)
這道題是能夠做到空間復(fù)雜度O(1)的。
當(dāng)前如果str1[i]贪嫂！=str2[j]寺庄，那么直接dp[i][j]=0。也就是說力崇，我在當(dāng)前位置做決策斗塘，我只需要我左上角的值，也就是只與斜線上左上角的值有關(guān)亮靴。
這已經(jīng)不代表dp矩陣了逛拱，只是str1和str2一種對應(yīng)關(guān)系，想象成一張表台猴，這種對應(yīng)關(guān)系是朽合，要么斜線是連續(xù)遞增，要么就是突然間變成0饱狂，可以用一個(gè)變量把這條線上所有的值都算出來曹步。
