動態規劃,它來了

語言: CN / TW / HK

前言

大家好,我是bigsai,好久不見,甚是想念(天天想念)!

很久前就有小夥伴被動態規劃所折磨,確實,很多題動態規劃確實太難看出了了,甚至有的題看了題解理解起來都費勁半天。

動態規劃的範圍雖然確實是很廣很難,但是從整個動態規劃出現的頻率來看,這幾種基礎的動態規劃理解容易,學習起來壓力不大,並且出現頻率非常高。

這幾個常見的動態規劃有:連續子陣列最大和,子陣列的最大乘積,最長遞增子序列(LIS),最長公共子序列(LCS),最長公共子串,最長公共子串,不同子序列。

什麼是動態規劃

首先很多人問,何為動態規劃? 動態規劃 (Dynamic Programming,DP)是運籌學的一個分支,是求解決策過程最優化的過程。通俗一點動態規劃就是從下往上(從前向後)階梯型求解數值。

那麼動態規劃和遞迴有什麼區別和聯絡?

總的來說動態規劃從前向後,遞迴從後向前,兩者策略不同,並且一般動態規劃效率高於遞迴。

不過都要考慮初始狀態,上下層資料之間的聯絡。很多時候用動態規劃能解決的問題,用遞迴也能解決不過很多時候效率不高可能會用到記憶化搜尋。

不太明白?

就拿求解斐波那契額數列來說,如果直接用遞迴不優化,那麼複雜度太多會進行很多重複的計算。

但是利用記憶化你可以理解為一層快取,將求過的值存下來下次再遇到就直接使用就可以了。

實現記憶化搜尋求斐波那契程式碼為:

static long F(int n,long record[])
{
if(n==1||n==2) {return 1;}
if(record[n]>0)
return record[n];
else
record[n]=F(n-1,record)+F(n-2,record);
return record[n];
}
public static void main(String[] args) {
int n=6;
long[] record = new long[n+1];
System.out.println(F(n,record));
}

而動態規劃的方式你可以從前往後邏輯處理,從第三個開始每個dp都是前兩個dp之和。

 public int fib(int n) {
int dp[]=new int[n+1];
dp[0]=0;
dp[1]=1;
for(int i=2;i<n+1;i++){
dp[i]=dp[i-1]+dp[i-2];
}
return dp[n];
}

當然動態規劃也能有很多空間優化,有些只用一次的值,你可以用一些變數去替代。有些二維陣列很大也可以用一維陣列交替替代。當然動態規劃專題很大,有很多比如樹形dp、狀壓dp、揹包問題等等經常出現在競賽中,能力有限這裡就將一些出現筆試高頻的動態規劃!

連續子陣列最大和

給定一個整數陣列 nums ,找到一個具有最大和的連續子陣列(子陣列最少包含一個元素),返回其最大和。

示例:

輸入: [-2,1,-3,4,-1,2,1,-5,4]

輸出: 6

解釋: 連續子陣列 [4,-1,2,1] 的和最大,為 6。

dp的方法就是O(n)的方法。 如果dp[i]表示以第i個結尾的最大序列和 ,而這個dp的狀態方程為:

dp[0]=a[0]
dp[i]=max(dp[i-1]+a[i],a[i])

也不難解釋,如果以前一個為截至的最大子序列和大於0,那麼就連線本個元素,否則本個元素就自立門戶。

實現程式碼為:

public int maxSubArray(int[] nums) {
int dp[]=new int[nums.length];
int max=nums[0];
dp[0]=nums[0];
for(int i=1;i<nums.length;i++)
{
dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);
if(dp[i]>max)
max=dp[i];
}
return max;
}

ps:有小夥伴問那求可以不連續的陣列最大和呢?你好好想想列舉一下正的收入囊中,那個問題沒意義的。

連續子陣列最大乘積

給你一個整數陣列 nums ,請你找出陣列中乘積最大的連續子陣列(該子陣列中至少包含一個數字),並返回該子陣列所對應的乘積。

示例 :

輸入: [2,3,-2,4]

輸出: 6

解釋: 子陣列 [2,3] 有最大乘積 6。

連續子陣列的最大乘積,這也是一道經典的動態規劃問題,但是和普通動態規劃又有點小不同。

如果資料中都是非負數,對於連續陣列的最大乘積,那樣處理起來和前面連續子陣列最大和處理起來有些相似,要麼和前面的疊乘,要麼自立門戶。

dp[0]=nums[0]
dp[i]=max(dp[i-1]*a[i],a[i])

但是這裡面的資料會出現 負數 ,乘以一個負數它可能從最大變成最小,並且還有負負得正就又可能變成最大了。

這時候該怎麼考慮呢?

容易,我們開兩個dp,一個 dpmax[] 記錄乘積的最大值,一個 dpmin[] 記錄乘積的最小值。然後每次都更新dpmax和dpmin不管當前值是正數還是負數.這樣通過這兩個陣列就可以記錄乘積的 絕對值最大

動態方程也很容易

dpmax[i]=max(dpmax[i-1]*nums[i],dpmin[i-1]*nums[i],nums[i])
dpmin[i]=min(dpmax[i-1]*nums[i],dpmin[i-1]*nums[i],nums[i])

看一個過程就能理解明白,dpmin就是起到中間過度的作用,記錄一些可能的 負極值 以防備用。結果還是dpmax中的值。

最長遞增子序列

最長遞增子序列,也稱為LIS,是出現非常高頻的動態規劃演算法之一。這裡對應力扣300

給你一個整數陣列 nums ,找到其中最長嚴格遞增子序列的長度。

子序列是由陣列派生而來的序列,刪除(或不刪除)陣列中的元素而不改變其餘元素的順序。例如,[3,6,2,7] 是陣列 [0,3,1,6,2,2,7] 的子序列。

輸入:nums = [0,1,0,3,2,3]

輸出:4

解釋:最長遞增子序列是 [0,1,2,3],因此長度為 4 。

對於最長遞增子序列,如果不考慮動態規劃的方法,使用暴力列舉其實還是比較麻煩的,因為你不知道遇到比前面元素大的是否要遞增。

比如 1 10 3 11 4 5,這個序列不能選取1 10 11而1 3 4 5才是最大的,所以暴力列舉所有情況的時間複雜度還是非常高的。

如果我們採取動態規劃的方法,建立的 dp[] 陣列,dp[i]表示以 nums[i] 結尾的最長遞增子序列,而dp[i]的求解方式就是列舉i號前面的元素和對應結尾的最長子序列,找到一個元素值小於 nums[i] 並且遞增序列最長,這樣的時間複雜度為O(n2)。

狀態轉移方程為:

dp[i]=max(dp[j])+1, 其中0≤j<i且num[j]<num[i]

具體流程為:

實現程式碼為:

class Solution {
public int lengthOfLIS(int[] nums) {
int dp[]=new int[nums.length];
int maxLen=1;
dp[0]=1;
for(int i=1;i<nums.length;i++){
int max=0;//統計前面 末尾數字比自己小 最長遞增子串
for(int j=0;j<i;j++){//列舉
//結尾數字小於當前數字 並且長度大於記錄的最長
if(nums[j]<nums[i]&&dp[j]>max){
max=dp[j];
}
}
dp[i]=max+1;//前面最長 加上自己
if(maxLen<dp[i])
maxLen=dp[i];
}
return maxLen;
}
}

不過這道題還有一個優化,可以優化成O(nlogn)的時間複雜度。

我們用dp記錄以 nums[i] 結尾的最長子序列長度,縱觀全域性,我們希望在長度一致的情況下末尾的值能夠儘量的小!

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

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

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

實現程式碼為:

class Solution {
public int lengthOfLIS(int[] nums) {
int length[]=new int[nums.length];
int len=1;
length[0]=nums[0];
for(int i=1;i<nums.length;i++){
int left=0,right=len;
while (left<right){
int mid=left+(right-left)/2;
if(length[mid]<nums[i]){
left=mid+1;
}else {
right=mid;
}
}
length[left]=nums[i];
if(right==len)
len++;
}
return len;
}
}

最長公共子序列

最長公共子序列也成為LCS.出現頻率非常高!

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

一個字串的 子序列 是指這樣一個新的字串:它是由原字串在不改變字元的 相對順序 的情況下刪除某些字元(也可以不刪除任何字元)後組成的新字串。

例如,"ace" 是 "abcde" 的子序列,但 "aec" 不是 "abcde" 的子序列。

兩個字串的 公共子序列 是這兩個字串所共同擁有的子序列。

拿b c d d e和 a c e e d e舉例,其的公共子串為c d e。如果使用暴力,複雜度太高會直接超時,就需要使用動態規劃。兩個字串匹配,我們設立二維 dp[][] 陣列, dp[i][j] 表示text1串第i個結尾,text2串第j個結尾的 最長公共子串的長度

這裡核心就是要搞懂狀態轉移,分析 dp[i][j] 的轉換情況,當到達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])

所以整個狀態轉移方程為:

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]時

實現程式碼為:

class Solution {
public int longestCommonSubsequence(String text1, String text2) {
char ch1[]=text1.toCharArray();
char ch2[]=text2.toCharArray();
int dp[][]=new int[ch1.length+1][ch2.length+1];
for(int i=0;i<ch1.length;i++)
{
for(int j=0;j<ch2.length;j++)
{
if(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]);

}
}
return dp[ch1.length][ch2.length];
}
}

最長公共子串

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

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

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

核心的狀態轉移方程為:

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

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

不同子序列

不同子序列也會出現,並且有些難度,前面這篇不同子序列問題分析講的大家可以看看。

給定一個字串 s 和一個字串 t ,計算在 s 的子序列中 t 出現的個數。

字串的一個 子序列 是指,通過刪除一些(也可以不刪除)字元且不干擾剩餘字元相對位置所組成的新字串。(例如,"ACE" 是 "ABCDE" 的一個子序列,而 "AEC" 不是)

示例 :

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

分析:

這個問題其實就是上面有幾個pat的變形拓展,其基本思想其實是一致的,上面那題問的是有幾個pat,固定、且很短。但這裡面t串的長度不固定,所以處理上就要使用 陣列 來處理而不能直接if else。

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

但是有一點需要注意的就是在遍歷s串中第i個字母的時候, 遍歷t串比較不能從左向右而必須從右向左 。因為在遍歷s串的第i個字元在列舉dp陣列時候要求此刻資料是相對靜止的疊加(即同一層次不能產生影響),而從左往右進行遇到相同字元會對後面的值產生影響。區別的話可以參考下圖這個例子:

實現的程式碼為:

class Solution {
public int numDistinct(String s, String t) {
char s1[]=s.toCharArray();
char t1[]=t.toCharArray();
int dp[]=new int[t1.length+1];
dp[0]=1;//用來疊加

for(int i=0;i<s1.length;i++)
{
for(int j=t1.length-1;j>=0;j--)
{
if(t1[j]==s1[i])
{
dp[j+1]+=dp[j];
}
}
}
return dp[t1.length];
}
}

結語

至此,簡單的動態規劃算是分享完了。

大部分簡單動態規劃還是有套路的,你看到一些陣列問題、字串問題很有可能就暗藏動態規劃。動態規劃的套路跟遞迴有點點相似,主要是找到狀態轉移方程,有時候考慮問題不能一步想的太多(想太多可能就把自己繞進去了),而動態規劃就是要大家對數值上下轉換計算需要了解其中關係。

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