動(dòng)態(tài)規(guī)劃和遞歸有什么區(qū)別和聯(lián)系

實(shí)現(xiàn)代碼為：

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

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

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

例如 2,3,9,5 …… 在前面最長(zhǎng)的長(zhǎng)度為3 我們?cè)敢鈷仐?,3,9 而全部使用2,3,5 。也就是對(duì)于一個(gè)值，我們希望這個(gè)值能更新以它為結(jié)尾的最長(zhǎng)的序列的末尾值。

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

而這個(gè)思路的核心就是維護(hù)一個(gè)lenth[]數(shù)組，length[i]表示長(zhǎng)度為i的子序列末尾最小值，因?yàn)槲覀兠看?strong style="color:rgb(233,105,0);font-size:inherit;line-height:inherit;">順序增加一個(gè)長(zhǎng)度說(shuō)明這個(gè)值比前面的都大(做了充分比較)，所以這個(gè)數(shù)組也是個(gè)遞增的，遞增，那么在鎖定位置更新最大長(zhǎng)度序列尾值的時(shí)候可以使用二分法優(yōu)化。

實(shí)現(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;
}
}

最長(zhǎng)公共子序列

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

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

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

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

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

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

如果text1[i]==text2[j],因?yàn)閮蓚€(gè)元素都在最末尾的位置，所以一定可以匹配成功，換句話說(shuō)，這個(gè)位置的鄰居dp值不可能大于他（最多相等）。所以這個(gè)時(shí)候就是dp[i][j]=dp[i-1][j-1]+1;

如果text1[i]!=text2[j]，就有兩種可能性，我們知道的鄰居有dp[i-1][j],dp[i][j-1]，很多人還會(huì)想到dp[i-1][j-1]這個(gè)一定比前兩個(gè)小于等于，因?yàn)榫褪乔懊?strong style="color:rgb(233,105,0);font-size:inherit;line-height:inherit;">兩個(gè)子范圍嘛！所以這時(shí)就相當(dāng)于末尾匹配不成，就要看看鄰居能匹配的最大值啦，此時(shí)dp[i][j]=max(dp[i][j-1],dp[i-1][j])。

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

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

實(shí)現(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];
}
}

最長(zhǎng)公共子串

給定兩個(gè)字符串str1和str2,輸出兩個(gè)字符串的最長(zhǎng)公共子串。

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

如何分析呢? 和上面最長(zhǎng)公共子序列的分析方式相似，要進(jìn)行動(dòng)態(tài)規(guī)劃匹配，并且邏輯上處理更簡(jiǎn)單，只要當(dāng)前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]時(shí)
dp[i][j]=0//text1[i]!=text2[j]時(shí)

這里代碼和上面很相似就不寫啦，但是有個(gè)問(wèn)題有的會(huì)讓你輸出最長(zhǎng)字符串之類，你要記得用一些變量存儲(chǔ)值。

不同子序列

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

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

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

示例 ：

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

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

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

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

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

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

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é)語(yǔ)

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

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

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