實現(xiàn)代碼為：

classSolution{
publicintlengthOfLIS(int[]nums){
intdp[]=newint[nums.length];
intmaxLen=1;
dp[0]=1;
for(inti=1;iintmax=0;//統(tǒng)計前面末尾數(shù)字比自己小最長遞增子串
for(intj=0;j//枚舉
//結(jié)尾數(shù)字小于當前數(shù)字并且長度大于記錄的最長
if(nums[j]max){
max=dp[j];
}
}
dp[i]=max+1;//前面最長加上自己
if(maxLenreturnmaxLen;
}
}

不過這道題還有一個優(yōu)化，可以優(yōu)化成O(nlogn)的時間復(fù)雜度。

我們用dp記錄以nums[i]結(jié)尾的最長子序列長度,縱觀全局，我們希望在長度一致的情況下末尾的值能夠盡量的小！

例如 2,3,9,5 …… 在前面最長的長度為3 我們愿意拋棄2,3,9 而全部使用2,3,5 。也就是對于一個值，我們希望這個值能更新以它為結(jié)尾的最長的序列的末尾值。

如果這個值更新不了最長的序列，那就嘗試更新第二長的末尾值以防待用。例如 2,3,9,5,4,5 這個序列2,3,5更新2,3,9;然后2,3,4更新2,3,5 為最長的2,3,4,5做鋪墊。

而這個思路的核心就是維護一個lenth[]數(shù)組，length[i]表示長度為i的子序列末尾最小值，因為我們每次順序增加一個長度說明這個值比前面的都大(做了充分比較)，所以這個數(shù)組也是個遞增的，遞增，那么在鎖定位置更新最大長度序列尾值的時候可以使用二分法優(yōu)化。

實現(xiàn)代碼為：

classSolution{
publicintlengthOfLIS(int[]nums){
intlength[]=newint[nums.length];
intlen=1;
length[0]=nums[0];
for(inti=1;iintleft=0,right=len;
while(leftintmid=left+(right-left)/2;
if(length[mid]1;
}else{
right=mid;
}
}
length[left]=nums[i];
if(right==len)
len++;
}
returnlen;
}
}

最長公共子序列

最長公共子序列也成為LCS.出現(xiàn)頻率非常高！

給定兩個字符串 text1 和 text2，返回這兩個字符串的最長 公共子序列 的長度。如果不存在 公共子序列 ，返回 0 。

一個字符串的 子序列 是指這樣一個新的字符串：它是由原字符串在不改變字符的相對順序的情況下刪除某些字符（也可以不刪除任何字符）后組成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
兩個字符串的 公共子序列 是這兩個字符串所共同擁有的子序列。

拿b c d d e和 a c e e d e舉例，其的公共子串為c d e。如果使用暴力，復(fù)雜度太高會直接超時，就需要使用動態(tài)規(guī)劃。兩個字符串匹配，我們設(shè)立二維dp[][]數(shù)組，dp[i][j]表示text1串第i個結(jié)尾，text2串第j個結(jié)尾的最長公共子串的長度。

這里核心就是要搞懂狀態(tài)轉(zhuǎn)移，分析dp[i][j]的轉(zhuǎn)換情況，當?shù)竭_i,j時候：

如果text1[i]==text2[j],因為兩個元素都在最末尾的位置，所以一定可以匹配成功，換句話說，這個位置的鄰居dp值不可能大于他（最多相等）。所以這個時候就是dp[i][j]=dp[i-1][j-1]+1;

如果text1[i]!=text2[j]，就有兩種可能性，我們知道的鄰居有dp[i-1][j],dp[i][j-1]，很多人還會想到dp[i-1][j-1]這個一定比前兩個小于等于，因為就是前面兩個子范圍嘛！所以這時就相當于末尾匹配不成，就要看看鄰居能匹配的最大值啦，此時dp[i][j]=max(dp[i][j-1],dp[i-1][j])。

所以整個狀態(tài)轉(zhuǎn)移方程為：

dp[i][j]=dp[i-1][j-1]+1//text1[i]==text2[j]時
dp[i][j]=max(dp[i][j-1],dp[i-1][j])//text1[i]!=text2[j]時

實現(xiàn)代碼為：

classSolution{
publicintlongestCommonSubsequence(Stringtext1,Stringtext2){
charch1[]=text1.toCharArray();
charch2[]=text2.toCharArray();
intdp[][]=newint[ch1.length+1][ch2.length+1];
for(inti=0;ifor(intj=0;jif(ch1[i]==ch2[j])
{
dp[i+1][j+1]=dp[i][j]+1;
}
else
dp[i+1][j+1]=Math.max(dp[i][j+1],dp[i+1][j]);

}
}
returndp[ch1.length][ch2.length];
}
}

最長公共子串

給定兩個字符串str1和str2,輸出兩個字符串的最長公共子串。

例如 abceef 和a2b2cee3f的最長公共子串就是cee。公共子串是兩個串中最長連續(xù)的相同部分。

如何分析呢? 和上面最長公共子序列的分析方式相似，要進行動態(tài)規(guī)劃匹配，并且邏輯上處理更簡單，只要當前i,j不匹配那么dp值就為0，如果可以匹配那么就變成dp[i-1][j-1] + 1

核心的狀態(tài)轉(zhuǎn)移方程為：

dp[i][j]=dp[i-1][j-1]+1//text1[i]==text2[j]時
dp[i][j]=0//text1[i]!=text2[j]時

這里代碼和上面很相似就不寫啦，但是有個問題有的會讓你輸出最長字符串之類，你要記得用一些變量存儲值。

不同子序列

不同子序列也會出現(xiàn)，并且有些難度，前面這篇不同子序列問題分析講的大家可以看看。

給定一個字符串 s 和一個字符串 t ，計算在 s 的子序列中 t 出現(xiàn)的個數(shù)。

字符串的一個 子序列 是指，通過刪除一些（也可以不刪除）字符且不干擾剩余字符相對位置所組成的新字符串。（例如，"ACE" 是 "ABCDE" 的一個子序列，而 "AEC" 不是）

示例 ：

輸入：s ="rabbbit",t="rabbit"
輸出：3
解釋：
如下圖所示,有3種可以從s中得到"rabbit"的方案。
(上箭頭符號^表示選取的字母)
rabbbit
^^^^^^
rabbbit
^^^^^^
rabbbit
^^^^^^

分析：
這個問題其實就是上面有幾個pat的變形拓展，其基本思想其實是一致的，上面那題問的是有幾個pat，固定、且很短。但這里面t串的長度不固定，所以處理上就要使用數(shù)組來處理而不能直接if else。

這題的思路肯定也是動態(tài)規(guī)劃dp了，dp[j]的意思就是t串中[0,j-1]長字符在s中能夠匹配的數(shù)量(當然這個值從前往后是動態(tài)變化的)，數(shù)組大小為dp[t.length+1]。在遍歷s串的每一個元素都要和t串中所有元素進行對比看看是否相等，如果s串枚舉到的這個串和t串中的第j個相等。那么dp[j+1]+=dp[j]。你可能會問為啥是dp[j+1],因為第一個元素匹配到需要將數(shù)量+1，而這里為了避免這樣的判斷我們將dp[0]=1,這樣t串的每個元素都能正常的操作。

但是有一點需要注意的就是在遍歷s串中第i個字母的時候，遍歷t串比較不能從左向右而必須從右向左。因為在遍歷s串的第i個字符在枚舉dp數(shù)組時候要求此刻數(shù)據(jù)是相對靜止的疊加(即同一層次不能產(chǎn)生影響)，而從左往右進行遇到相同字符會對后面的值產(chǎn)生影響。區(qū)別的話可以參考下圖這個例子：

實現(xiàn)的代碼為：

classSolution{
publicintnumDistinct(Strings,Stringt){
chars1[]=s.toCharArray();
chart1[]=t.toCharArray();
intdp[]=newint[t1.length+1];
dp[0]=1;//用來疊加

for(inti=0;ifor(intj=t1.length-1;j>=0;j--)
{
if(t1[j]==s1[i])
{
dp[j+1]+=dp[j];
}
}
}
returndp[t1.length];
}
}

結(jié)語

至此，簡單的動態(tài)規(guī)劃算是分享完了。

大部分簡單動態(tài)規(guī)劃還是有套路的，你看到一些數(shù)組問題、字符串問題很有可能就暗藏動態(tài)規(guī)劃。動態(tài)規(guī)劃的套路跟遞歸有點點相似，主要是找到狀態(tài)轉(zhuǎn)移方程，有時候考慮問題不能一步想的太多(想太多可能就把自己繞進去了)，而動態(tài)規(guī)劃就是要大家對數(shù)值上下轉(zhuǎn)換計算需要了解其中關(guān)系。

對于復(fù)雜dp問題或者很多套一層殼確實很難看出來，但是掌握上面的常見dp問題和背包問題，就可以解決大部分動態(tài)規(guī)劃問題啦(畢竟咱們不是搞競賽遇到的還是偏簡單或者中等難度的)。