最長子序列可以說是剛接觸動(dòng)態(tài)規(guī)劃的人經(jīng)常遇見也不得不解決的問題，最常見的有兩種，一種是最長公共子序列（LCS），還有一個(gè)是最長上升子序列（LIS）。今天我就總結(jié)下這兩個(gè)的做法。

?

一：最長公共子序列（LCS）

　　題目描述：給你兩個(gè)數(shù)組，可以是數(shù)字的，也可以是字符串，我們假設(shè)是數(shù)字的！舉個(gè)例子：

　　　　X? =? 1, 5, 6, 4, 1, 3, 7

　　　　Y? =? 1, 1, 6, 8, 3, 4, 7

　　求一個(gè)新的數(shù)組S，該數(shù)組中的每個(gè)數(shù)均是X和Y數(shù)組中的公共數(shù)，并滿足原數(shù)組中數(shù)字的前后關(guān)系，這樣的數(shù)組有很多個(gè)，比如說　　　　　　　　? （1,1），（1,1,3,7），（1,6,7）等。同時(shí)S數(shù)組要是長度最長的那個(gè)，像上面的（1,1,3,7），長度是4，那么即為所求解！

　　做DP題目最重要的一點(diǎn)是能正確的構(gòu)造出DP函數(shù)，如果能很好的構(gòu)造出來，就成功一半了。

　　dp[i][j] 表示X數(shù)組的前i位和Y數(shù)組的前j位之前的LCS，那么它可以由前面三個(gè)狀態(tài)推出來。

　　　　　　　　　　　0???????????????????????????????? if(i=0 || j=0) --初始化，不難理解，不管是X還是Y數(shù)組，只要有一個(gè)長度是0，那么S數(shù)組就是0

　　　　　　dp[i][j] = max(dp[i-1][j],dp[i][j-1]??? if(i,j>0 && X[i] != Y[j]) --S數(shù)組沒有添加數(shù)字，那么只能從前面繼承來，一個(gè)從X,一個(gè)從Y，看那個(gè)大

　　　　　　　　　　　dp[i-1][j-1] + 1????????????? if(i,j>0 && X[i] == Y[j]) --如果是兩個(gè)相同，當(dāng)然是把S數(shù)組加1，可以看成X和Y都繼承了

　　　　代碼很簡單，兩個(gè)for循環(huán)就可以了。

二：最長遞增子序列（LIS）

　　題目描述：給你一個(gè)數(shù)組，如X數(shù)組，X = 1,2,3,6,5,7,4,8,6。

　　求一個(gè)新的數(shù)組S，該數(shù)組中的每個(gè)數(shù)均是X數(shù)組中的數(shù)，且對S中任意兩個(gè)數(shù)S[i]，S[j]滿足 j>i && s[j]>s[i]。同時(shí)S數(shù)組要是長度最長的那個(gè)，像（1,2,3,6,7,8）和（1,2,3,5,7,8），長度是6，即為所求解。

　　dp[i]表示以X數(shù)組中的第i個(gè)元素為S數(shù)組的底元素的最長子序列的長度。這樣又可以變成子問題來求解了，

　　dp[i] = max(dp[j]) + 1??? 0<j<i? &&? X[i] > num[j]。就是在i前面找一個(gè)符合條件的最長子序列。

??? 對這個(gè)題目來說，dp方程還是比較容易推出來和理解的，但你可以發(fā)現(xiàn)，時(shí)間復(fù)雜度是O（n^2）的，這對許多題目都是不能接受的，所以你必須進(jìn)行優(yōu)化。這就牽扯到一個(gè)問題，最長遞增子序列的O(n*lgn)做法。

??? 做法如下：首先給你一個(gè)數(shù)組stack，用來存儲最長遞增子序列（按照遞增的要求，即數(shù)組的最頂端的數(shù)最大，最尾的數(shù)最小，如果說用棧的話你也許更好理解），對X數(shù)組進(jìn)行線掃，如果X[i]大于數(shù)組的頂端元素(最大值)，那么把這個(gè)數(shù)加入到stack數(shù)組中來，如果比頂端元素小，那么在stack數(shù)組中找到第一個(gè)大于X[i]的數(shù)，并用X[i]替換掉。因?yàn)閟tack數(shù)組是有序的，在你找第一個(gè)大于X[i]的數(shù)的時(shí)候你就可以用二分查找來做，這就是優(yōu)化所在！

?

??? 這兩個(gè)都是很簡單的dp題目，但也包含了動(dòng)態(tài)規(guī)劃思想，在后面的很多題目中你會發(fā)現(xiàn)都會不經(jīng)意中用到這種思想，所以很好的理解他們是必須的。但動(dòng)態(tài)規(guī)劃博大精深，就因?yàn)樗麤]有固定的程序，許多都是思想，所以僅僅知道這兩個(gè)是遠(yuǎn)遠(yuǎn)不夠的！

?

?

?

最長子序列