個人主頁：敲上癮-CSDN博客

動態(tài)規(guī)劃

• 基礎(chǔ)dp：基礎(chǔ)dp——動態(tài)規(guī)劃-CSDN博客
• 多狀態(tài)dp：多狀態(tài)dp——動態(tài)規(guī)劃-CSDN博客

目錄

一、解題技巧

二、最大子數(shù)組和

三、乘積最大子數(shù)組

四、最長湍流子數(shù)組

五、單詞拆分

---

一、解題技巧

區(qū)分子數(shù)組（子串）與子序列：

• 子數(shù)組（子串）：在數(shù)列中的一段連續(xù)的元素組成的新數(shù)列，中間不可間斷。
• 子序列：在數(shù)列中從左往右依次挑選出元素組成的新數(shù)列，或者說在數(shù)列中隨意刪除一些元素后，剩下的元素組成的新數(shù)列。

用動態(tài)規(guī)劃做子數(shù)組類的題時，對于狀態(tài)表示我們可以直接設(shè)：

• dp[i]為以i元素結(jié)尾的子數(shù)組的... ...?

????????后面就根據(jù)具體的題目要求填寫，可能是子數(shù)組的和或者子數(shù)組的積等等，無論如何都可以以i元素結(jié)尾的子數(shù)組為研究對象去思考問題，如果解決不了就嘗試增加狀態(tài)，但研究對象不要改變。如果還解決不了那么再考慮改變或增加研究對象。

二、最大子數(shù)組和

狀態(tài)表示

如上技巧所述，我們直接設(shè)狀態(tài)轉(zhuǎn)移方程：

• dp[i]表示：以i位置結(jié)尾的子數(shù)組的最大和。

接下來只需要去嘗試是否能寫出正確的狀態(tài)轉(zhuǎn)移方程，如果能那么狀態(tài)表示就是對的。

狀態(tài)轉(zhuǎn)移方程：

以i位置結(jié)尾的子數(shù)組我們可以分為兩種：

1. nums[i]單獨構(gòu)成一個子數(shù)組
2. nums[i]和以i-1結(jié)尾的最大和子數(shù)組組合成的子數(shù)組。

????????那么這個以i-1結(jié)尾的最大子數(shù)組的值就是一個重復子問題，我們假設(shè)在前面已經(jīng)計算過了，即dp[i-1]，然后需要注意兩種情況只能取一種。那么：

• dp[i] = max(nums[i]+dp[i-1]，nums[i])

初始化

初始化的目的主要有兩個：

• 保證填表的時候不越界。
• 保證填表的正確性。

????????因為這里有i-1，所以如果從0開始填表可能會越界，通常有兩種解決方案：

????????方法一：把dp[0]初始化（即dp[0]=nums[0]），然后從dp[1]位置開始填表（即從nums[1]位置開始記錄）。

????????方法二：開辟一個n+1的空間（n=nums.size()），讓dp[0]=0（需要根據(jù)具體情況具體分析），然后從dp[1]位置開始填寫，而dp[1]記錄的是nums[0]的情況，也就是錯開一位進行記錄，所以需要注意映射關(guān)系。

? ? ? ? 這題看似方法一更簡潔，但對于其他題可能需要做更復雜的邊界判斷。所以在做動規(guī)題時更推薦使用方法二來解決邊界問題。

填表順序

? ? ? ? 從左往右。

返回值

? ? ? ? dp表中的最大值。

代碼示例：

class Solution 
{
public:int maxSubArray(vector<int>& nums){int n=nums.size(),ret=INT_MIN;vector<int> dp(n+1);for(int i=1;i<n+1;i++){dp[i]=max(nums[i-1],nums[i-1]+dp[i-1]);ret=max(ret,dp[i]);}    return ret;}
};

三、乘積最大子數(shù)組

狀態(tài)表示

同樣的我們假設(shè)狀態(tài)表示為：

? ? ? ? dp[i]表示：以i位置結(jié)尾的子數(shù)組的最大乘積。

????????那么狀態(tài)轉(zhuǎn)移方程dp[i]=max(dp[i-1]*nums[i]，nums[i])，我們想一想這樣對嗎？比如dp[i-1]*nums[i]，nums[i]乘以一個最大積的子數(shù)組就是最大嗎？

? ? ? ? 如果nums是一個負數(shù)不就變成最小乘積了嗎，反之nums[i]小于0時乘以一個最小的數(shù)才能成為最大積。

? ? ? ? 所以當nums[i]小于0時我們需要知道以i-1結(jié)尾的子數(shù)組的最小積。

所以狀態(tài)表示為：

• f[i]表示：以i位置結(jié)尾的子數(shù)組的最大乘積。
• g[i]表示：以i位置結(jié)尾的子數(shù)組的最小乘積。

狀態(tài)轉(zhuǎn)移方程

• nums[i]>=0：
  • f[i] = max(f[i-1]*nums[i]，nums[i])
  • g[i] = min(g[i-1]*nums[i]，nums[i])
• nums[i] < 0:
  • f[i] = max(g[i-1]*nums[i]，nums[i])
  • g[i] = min(f[i-1]*nums[i]，nums[i])?? ? ? ?

或：

• f[i]=max(nums[i],max(nums[i]*f[i-1],nums[i]*g[i-1]));
• g[i]=min(nums[i],min(nums[i]*f[i-1],nums[i]*g[i-1]));

初始化

? ? ? ? 與上一題相同，為防止越界我們給兩個dp表都多開辟一個空間，映射關(guān)系錯開一位。

? ? ? ? 然后把兩個dp表都初始化為1，因為這里是乘法，如果使用默認的0值那么這個結(jié)果都是0。

注：dp[0]是我們?yōu)榉乐乖浇缣砑由系奶摂M位置，它的值需要使得后面的填表正確。

填表順序

????????從左往右，f表和g表一起填。

返回值

????????f表中的最大值。

代碼示例：

class Solution {
public:int maxProduct(vector<int>& nums){int n=nums.size(), ret=INT_MIN;;vector<int> f(n+1,1),g(n+1,1);for(int i=1;i<=n;i++){f[i]=max(nums[i-1],max(nums[i-1]*f[i-1],nums[i-1]*g[i-1]));g[i]=min(nums[i-1],min(nums[i-1]*f[i-1],nums[i-1]*g[i-1]));ret=max(ret,f[i]);}return ret;}
};

四、最長湍流子數(shù)組

題目的核心就一句話：比較符號在子數(shù)組中的每個相鄰元素對之間翻轉(zhuǎn)。

然后找到滿足這樣的條件的最長子數(shù)組。

狀態(tài)表示

假設(shè)狀態(tài)表示為：

? ? ? ? dp[i]表示：以i結(jié)尾的最長湍流子數(shù)組。

我們把數(shù)據(jù)的大小波動抽象成一條折線，如下把示例1化為折線圖：

結(jié)果取該段：

????????也就是子數(shù)組要滿足前一個元素是上升趨勢那么下一個元素必須是下降，如果前一個元素是下降趨勢那么下一個元素必須是上升。

我們在做狀態(tài)轉(zhuǎn)移方程中主要是考慮兩種情況，

1. nums[i]單獨構(gòu)成一個子數(shù)組
2. nums[i]接到前一個元素結(jié)尾構(gòu)成的子數(shù)組中。

第2種情況又需要分情況討論，

• nums[i] < nums[i-1]：只有前面的子數(shù)組最終狀態(tài)是呈現(xiàn)上升趨勢時nums[i]才能接上。
• nums[i] > nums[i-1]：只有前面的子數(shù)組最終狀態(tài)是呈現(xiàn)下降趨勢時nums[i]才能接上。
• nums[i]==nums[i-1]：不能接入前面子數(shù)組。

所以我們需要把狀態(tài)轉(zhuǎn)移細分為兩種狀態(tài)：

• f[i]表示：以i結(jié)尾并且最后一個元素呈上升趨勢的最長湍流子數(shù)組的長度。
• g[i]表示：以i結(jié)尾并且最后一個元素呈下降趨勢的最長湍流子數(shù)組的長度。

狀態(tài)轉(zhuǎn)移方程

• nums[i] < nums[i-1]：
  • f[i]=1
  • g[i]=f[i-1]+1
• nums[i] > nums[i-1]：
  • f[i]=g[i-1]+1
  • g[i]=1
• nums[i]==nums[i-1]：
  • f[i]=1
  • g[i]=1

????????因為任意一個子數(shù)組，最小的長度都是1，所以可以把兩個dp表都初始化為1，那么狀態(tài)轉(zhuǎn)移方程可簡化為：

• nums[i] < nums[i-1]：g[i]+=f[i-1]
• nums[i] > nums[i-1]：f[i]+=g[i-1]

初始化

? ? ? ??為防止越界我們給兩個dp表都多開辟一個空間，映射關(guān)系錯開一位。

? ? ? ? 然后把兩個dp表都初始化為1。

填表順序

? ? ? ? 從左往右，f表和g表同時填寫。

返回值

? ? ? ? f表和g表中的最大那個元素

代碼示例：

class Solution {
public:int maxTurbulenceSize(vector<int>& arr){int n=arr.size(),ret=1;vector<int> f(n,1),g(n,1);for(int i=1;i<n;i++){if(arr[i]<arr[i-1]) g[i]+=f[i-1];if(arr[i]>arr[i-1]) f[i]+=g[i-1];ret=max(ret,max(f[i],g[i]));}    return ret;}
};

五、單詞拆分

狀態(tài)表示

根據(jù)經(jīng)驗直接設(shè)狀態(tài)表示：

• dp[i]表示：從0到i位置結(jié)尾的字符串是否能被字典中的單詞表示（bool類型）。

狀態(tài)轉(zhuǎn)移方程

? ? ? ? 因為在填寫i時以前的每個子串是否能由字典表示已經(jīng)知道，儲存在dp表中。那么我們只需要找到任意一個j（0<=j<i）使得dp[j]=true，并且子字符串[j+1，i]能用字典表示，那么dp[i]=true，否則dp[i]=false。

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

• dp[i] = (dp[i-1]&&s[i，i]能用字典表示) || (dp[i-2]&&s[i-1，i]能用字典表示) || ... ... ||(dp[0]&&s[1，i]能用字典表示)

注：s[i-1，i]表示字符串中i-1到i這個子串。

初始化

? ? ? ??為了讓第一個字符元素也討論進來，我們創(chuàng)建n+1的dp表，并把dp[0]初始化為true。

填表順序

? ? ? ? 從左往右

返回值

? ? ? ? return dp[n]

代碼示例：

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict){int n=s.size();unordered_set<string> st(wordDict.begin(),wordDict.end());vector<bool> dp(n+1);dp[0]=true;for(int i=1;i<=n;i++){for(int j=0;j<i;j++){if(dp[j]==false) continue;if(st.count(string(s.begin()+j,s.begin()+i))){dp[i]=true;break;}}}   return dp[n];}
};

好題推薦：

• 53.?最大子數(shù)組和
• 918.?環(huán)形子數(shù)組的最大和
• 152.?乘積最大子數(shù)組
• 1567.?乘積為正數(shù)的最長子數(shù)組長度
• 413.?等差數(shù)列劃分
• 978.?最長湍流子數(shù)組
• 139.?單詞拆分
• 467.?環(huán)繞字符串中唯一的子字符串

非常感謝您能耐心讀完這篇文章。倘若您從中有所收獲，還望多多支持呀！