dp笔记：关于DP算法和滚动数组优化的思考
從網(wǎng)上總結(jié)了一些dp的套路以及對滾動數(shù)組的一些思考，現(xiàn)記錄如下，希望以后回顧此類算法時會有所幫助。
目錄
- 1、DP算法經(jīng)驗
- 1、DP算法核心：
- 2、DP算法類別以及例題
- 例1：三步問題
- 例2：最小路徑和
- 例3：乘積最大子數(shù)組
- 例4：[線性DP]最長上升子序列（LIS）
- 例5：[線性DP]俄羅斯套娃信封（排序降維后視作LIS）
- 例6：[線性DP]最長公共子序列（LCS、最基本的雙串匹配模型）
- 2、滾動數(shù)組優(yōu)化與背包問題
- 1、01背包問題
- 2、完全背包問題
- 3、多重背包問題
- 3、參考
1、DP算法經(jīng)驗
1、DP算法核心：
1、確定【DP狀態(tài)】
2、確定【DP狀態(tài)轉(zhuǎn)移方程】
其中DP狀態(tài)又需要考慮到兩點：
1、最優(yōu)子結(jié)構(gòu)
將原有問題化為一個個子問題，即子結(jié)構(gòu)。對于每一個子問題，其最優(yōu)值均由【更小規(guī)模的子問題的最優(yōu)值】推導(dǎo)過來
2、無后效性
我們只關(guān)心子問題的最優(yōu)值，不關(guān)心子問題的最優(yōu)值是怎樣的得到的。
2、DP算法類別以及例題
例1：三步問題
問題描述：樓梯有n階，一次可上1階，2階，或者3階。問總共偶多少種方案。同時，由于結(jié)果很大，請對結(jié)果取模MOD；
分析：
1、目標(biāo)：得到爬到n階樓梯的總方案數(shù)
2、子問題：爬i階樓梯時的總方案數(shù)
3、
【1】定義f[i]為爬i階樓梯時的總方案數(shù)，一般來說，爬第i階，它可能是由前1階爬1階、前2階爬2階、前3階爬3階得到的。
所以f[i] 的取值取決于：f[i-1]、f[i-2]、f[i-3]。
【2】f[i]取值與f[i-1]、f[i-2]、f[i-3]的數(shù)值如何得到無關(guān)。
【3】dp狀態(tài)轉(zhuǎn)移方程：
code：
//鏈接：https://zhuanlan.zhihu.com/p/180443034 class Solution {public:vector<int>f;int MOD=10000007;int waysToStep(int n){f.reszie(n+1);f[0]=1; //第0階方案為1for(int i=1;i<=n;i++){if(i==1)f[i]=f[i-1]; else if(i==2)f[i]=(f[i-1]+f[i-2])%MOD; elsef[i]=(f[i-1]+f[i-2]+f[i-3])%MOD;}return f[n];} };例2：最小路徑和
問題描述：給定一個包含非負(fù)整數(shù)mxn網(wǎng)格，找出一條從左上角到右下角的路徑，只能向右、向下，使路徑上的數(shù)字綜合最小
輸入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
輸出: 7
解釋: 因為路徑 1→3→1→1→1 的總和最小。
分析：
1、目標(biāo)：獲取網(wǎng)格grid[0][0]到grid[m][n]的最小數(shù)字和:f[m][n]
2、子問題：獲取網(wǎng)格grid[0][0]到grid[i][j]的最小數(shù)字和:f[i][j]
3、由題意可知到達(dá)網(wǎng)格grid[i][j]有兩種方法：一種是從它的左邊過來，一種是從它的上邊過來（因為只能向右、向下移動）
所以f[i][j] 的取值取決于：f[i-1][j] （左邊）、f[i][j-1] （上邊）
【2】f[i][j] 的取值取決于：f[i-1][j] （左邊）、f[i][j-1] （上邊）如何得到無關(guān)。
注意：若改為可以向上向下向左向右，且不能重復(fù)格子，則f[i][j-1]到f[i+1][j]所對應(yīng)的具體路徑會影響f[i][j]取值，則會不符合無后效性
【3】dp狀態(tài)轉(zhuǎn)移方程：
code:
//鏈接：https://zhuanlan.zhihu.com/p/180443034 class Solution {public:int minPathSum(vector<vector<int>> &grid){for(int i=0;i<grid.size();i++){for(int j=0;j<grid[0].size();j++){if(i==0 && j==0) continue; //grid[0][0]不需要修改int tp=1e9;//從左邊和上邊中選取一個較小的，作為路徑if(i>0) tp = min(tp,grid[i-1][j]);if(j>0) tp = min(tp,grid[i][j-1]); grid[i][j]+=tp;}}return grid[grid.size()-1][grid[0].size()-1];} }; //注意，這里為了節(jié)約空間，不新開辟數(shù)組，而是在grid數(shù)組的基礎(chǔ)上進(jìn)行修改，這樣就是在grid的基礎(chǔ)上加上左、上鄰值(最小路徑和)的最小值。推導(dǎo)：f[2][2] = f[2][1]+1=f[2][0]+2=f[1][0]+3=f[0][0]+6=1+6=7
例3：乘積最大子數(shù)組
問題描述：一個整數(shù)數(shù)組nums，找出數(shù)組中乘積最大的連續(xù)子數(shù)組（該子數(shù)組最少包含一個數(shù)字），并返回子數(shù)組對應(yīng)的乘積
輸入:[2,3,-2,4]
輸出: 6
解釋: 因為路徑 2 * 3=6
輸入:[-2,0,-1]
輸出: 0
分析：
1、目標(biāo)：在左端點為0，右端點為nums.size的連續(xù)區(qū)間中找到最大乘積
2、子問題：在左端點為0，右端點為i的連續(xù)區(qū)間中找到最大乘積
3、分析狀態(tài)定義是否符合最優(yōu)子結(jié)構(gòu)
nums=[2,-1,-2]
對應(yīng)的f[i]=[2,-1,4]
f[3] =4 != nums[3] !=f[2] * nums[3],所以f[i]與f[i-1]無關(guān)。
即DP轉(zhuǎn)臺最優(yōu)質(zhì)的無法由更小的規(guī)模的DP狀態(tài)最優(yōu)值推出，不符合【最優(yōu)子結(jié)構(gòu)】原則。
出錯原因：若nums[i]為負(fù)，則f[i] * nums[i]只會越來越小，因此需要分正負(fù)情況討論。
【1】、nums[i]>0
【2】、nums[i]<=0
f[i] = max(nums[i],以i-1為右端點的連續(xù)區(qū)間的最小乘積*nums[i])這樣就需要引入新的DP狀態(tài)
maxn[i]：表示以右端點的連續(xù)區(qū)間最大乘積
minn[i]：表示以右端點的連續(xù)區(qū)間最小乘積
maxn[i]、minn[i]由maxn[i-1]、minn[i-1]推導(dǎo)而出。
code:
例4：[線性DP]最長上升子序列（LIS）
題目描述：給定一個無序的整數(shù)數(shù)組，找到其中最長上升子序列的長度。
示例：
輸入：[10,9,2,5,3,7,101,18]
輸出：4
解釋：最長的上升子序列是[2,3,7,101],它的長度是4
思路：
1、先從小規(guī)模入手：
序列長度為1時=>ans=1
序列長度為2時=>Y[1]>=Y[2]的話，長度為1；Y[1]<Y[2],長度為2
DP狀態(tài)：f[i]表示僅考慮前i個數(shù)，以第i個數(shù)結(jié)尾的最長上升子序列的最大長度。
這種方法就是每一次嘗試尋找“可以接下去的”那一個數(shù)，換句話說，設(shè)原序列為a，則
當(dāng)aj<ai(j<i)且f[j]+1>f[i]時，f[i]=f[j]+1。
對于每一個數(shù)，他都是在“可以接下去”的中，從前面的最優(yōu)值+1轉(zhuǎn)移而來。通俗的來說，你肯定就是在所有能找到的里面取最好的一個。
因此，這個算法是可以求出正確答案的。復(fù)雜度很明顯，外層i枚舉每個數(shù)，內(nèi)層j枚舉目前i的最優(yōu)值，即 O(n2)
code：
例5：[線性DP]俄羅斯套娃信封（排序降維后視作LIS）
題目描述：
給定一些標(biāo)記了寬度和高度的信封，寬度和高度以整數(shù)對形式 (w, h) 出現(xiàn)。當(dāng)另一個信封的寬度和高度都比這個信封大的時候，這個信封就可以放進(jìn)另一個信封里，如同俄羅斯套娃一樣。請計算最多能有多少個信封能組成一組“俄羅斯套娃”信封（即可以把一個信封放到另一個信封里面）。
示例：（不允許旋轉(zhuǎn)信封）
輸入: envelopes = [[5,4],[6,4],[6,7],[2,3]]
輸出: 3
解釋: 最多信封的個數(shù)為 3, 組合為: [2,3] => [5,4] => [6,7]。
分析：
1、簡要概括題意，求一組二維上升子序列
，同時滿足：
由于裝入信封需要滿足兩個條件，而且信封的順序是無序的并且是可以調(diào)整順序的。所以我們可以先限制一維例如w，使信封按照w的大小，從小到大排列好，這樣就可以確定以w為準(zhǔn)則的話后面的總是可以將前面的包含。就只需要考慮h維度了。
接下來就和LIS步驟類似了：給定一個無序的整數(shù)數(shù)組（h維度上無序），找到其中最長上升子序列的長度。
code:
對這個問題有疑惑的，可以轉(zhuǎn)到我的記錄：
C++中的sort函數(shù)對二維數(shù)組排序是按照什么準(zhǔn)則？
例6：[線性DP]最長公共子序列（LCS、最基本的雙串匹配模型）
題目描述：
給定兩個字符串text1和text2，返回兩個字符串中的最長公共子序列長度。
例：
“ace”為"abcde"的子序列，若兩個字符串無公共子序列，返回0
IN: text1=“abcde”,text2=“ace”
OUT:3
IN:text1=“abc”,text2=“def”
OUT:0
tips:1<=text.length<=1000
1<=tex2.length<=1000
text中均為小寫英文字母
分析：
首先確定線性DP特點：DP狀態(tài)沿著各個維度線性增長。
目標(biāo)：獲取長度為n1的字符串與長度為n2的字符串的最長公共子序列
子問題：獲取長度為i的字符串與長度為j的字符串的最長公共子序列
確定dp狀態(tài)：f[i][j]:表示第一個字符串前i個字符與第二個字符串前j個字符的最長公共子序列長度
確定狀態(tài)轉(zhuǎn)移方程：
text1[i]與text2[j]有兩種結(jié)果，一個是相同，一個是不相同
1、如果text1[i]與text2[j]不相同 , f[i][j] 從f[i-1][j],f[i][j-1]選出最大的繼承下來，此時并沒有出現(xiàn)增長
f[i][j]=max(f[i-1][j],f[i][j-1]);
2、如果text1[i]與text2[j]相同，說明我們可以增加一種方式，且f[i][j]:表示第一個字符串前i個字符與第二個字符串前j個字符的最長公共子序列長度，所以f[i][j]是在f[i-1][j-1]的基礎(chǔ)上的來的。
f[i][j]=f[i-1][j-1]+1;
這樣的話復(fù)雜度為O(nm),n,m分別為text1和text2的長度
2、滾動數(shù)組優(yōu)化與背包問題
1、01背包問題
一共有N件物品，從第i(i從1開始)件物品的重量為w[i],價值為v[i].在總重量不超過背包承載上限W的情況下，求出能夠裝入背包的最大價值是多少？
分析步驟：
1、獲取總目標(biāo)：將N件物品裝進(jìn)限重為W的背包可以獲得的最大價值
2、子問題：將前i個物品裝進(jìn)限重為j的背包可以獲得的最大價值，0<=i<=N,0<=j<=W;
3、dp狀態(tài)定義以及檢查無后效性：dp[i][j]:表示將將前i個物品裝進(jìn)限重為j的背包可以獲得的最大價值，0<=i<=N,0<=j<=W;
再次分析：dp[i][j]由兩個部分組成：不裝入第i個物品、裝入第i個物品(假如能夠裝入的話)
即dp[i][j]只與dp[i-1][j] (不裝入)以及dp[i-1][j-w[i]]+v [i] (裝入第i個物品)有關(guān)，并且與子狀態(tài)的具體怎么得來無關(guān)，符合無后效性
4、dp狀態(tài)轉(zhuǎn)移方程定義：
已知dp[i][j]只與dp[i-1]j以及dp[i-1][j-w[i]] (裝入第i個物品)有關(guān)，那么具體是怎樣的關(guān)系：
dp[i][j]指的是將前i個物品裝進(jìn)限重為j的背包可以獲得的最大價值
dp[i-1][j]指的是將前i-1個物品裝進(jìn)限重為j的背包可以獲得的最大價值
dp[i-1][j-w[i]+v[i]指的是將前i-1個物品裝進(jìn)限重為j的背包可以獲得的最大價值+將第i個物品裝入的總價值.
dp[i][j]是在上述兩種可能的情況中較優(yōu)的一種，也就是價值更大的一種，所以可以這樣描述：
dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])
接下來介紹一種在DP算法比較常用的手法：滾動數(shù)組優(yōu)化
在上述的dp狀態(tài)方程中我們可以發(fā)現(xiàn)：dp[i][j] 只與dp[i-1][0,…,j-1]有關(guān)，也就是說dp狀態(tài)的二維數(shù)組的第一維在此時是浪費的，我們用到的只有第二維。所以可以采用滾動數(shù)組優(yōu)化，去掉dp中的第一維，變?yōu)槿缦滦问?#xff1a;
dp[j] = max(dp[j],dp[j-w[i]+v[i])
滾動數(shù)組是DP中的一種編程思想。簡單的理解就是讓數(shù)組滾動起來，每次都使用固定的幾個存儲空間，來達(dá)到壓縮，節(jié)省存儲空間的作用。起到優(yōu)化空間，主要應(yīng)用在遞推或動態(tài)規(guī)劃中（如01背包問題）。因為DP題目是一個自底向上的擴(kuò)展過程，我們常常需要用到的是連續(xù)的解，前面的解往往可以舍去。所以用滾動數(shù)組優(yōu)化是很有效的。利用滾動數(shù)組的話在N很大的情況下可以達(dá)到壓縮存儲的作用。
參考：《滾動數(shù)組》—滾動數(shù)組思想，運用在動態(tài)規(guī)劃當(dāng)中
此時滾動的方向尤其重要。
例如在遞推dp[j]時應(yīng)按W到0的順序，這樣才能保證推dp[j]時dp[j-w[i]]保存的是狀態(tài)dp[i-1,j-w[i]]的值
因為我們進(jìn)行操作的時候，是用一維數(shù)組dp同時存儲這一狀態(tài)和上一狀態(tài)的值的，從W到0遞推也就是說從后往前將i-1狀態(tài)更新為i狀態(tài)。
當(dāng)推導(dǎo)到j(luò)時，j往后的是i狀態(tài)。而j之前的是i-1狀態(tài)。要符合優(yōu)化之前的狀態(tài)方程，所以01背包問題的優(yōu)化數(shù)組滾動方向必然是從后往前的。
(不知道解釋的清不清楚。。。)
優(yōu)化后的核心代碼如下：需要注意的是滾動數(shù)組更新的結(jié)束條件是j>=w[i],意思就是是背包限重必須大于w[i]，也就是限重必須大于第i個物品的質(zhì)量(這是我們之前在談?wù)摖顟B(tài)方程說過的，dp[i][j]由兩個部分決定，一個是不裝入第i件物品，一個是裝入第i件物品(前提是裝的下)，這里就是為了滿足裝得下)
2、完全背包問題
問題描述：
每種物品有無限多個：一共有N種物品，每種物品有無限多個，從第i(i從1開始)種物品的重量為w[i],價值為v[i].在總重量不超過背包承載上限W的情況下，能夠裝入背包的最大價值為多少？
1、分析總目標(biāo)：將N種物品裝進(jìn)限重為W的背包可以獲得的最大價值（注意這里是種而不是件）
2、分析子狀態(tài)：將前i種物品裝進(jìn)限重為j的背包可以獲得的最大價值，0<=i<=N,0<=j<=W;
3、dp狀態(tài)定義以及檢查無后效性：dp[i][j]:表示將將前i種物品裝進(jìn)限重為j的背包可以獲得的最大價值，0<=i<=N,0<=j<=W;
再次分析：dp[i][j]由兩個部分組成：不裝入第i種物品、裝入第i種物品(假如能夠裝入的話)
即dp[i][j]只與dp[i-1][j] (不裝入)以及dp[i][j-w[i]]+v[i] (裝入第i種物品)有關(guān)，并且與子狀態(tài)的具體怎么得來無關(guān)，符合無后效性
注意：這里使用的是dp[i][j-w[i]]+v[i]，而不是dp[i-1][j-w[i]]+v[i]，兩者有什么區(qū)別呢？
首先確定一點：裝入第i種商品后還可以再繼續(xù)裝入第i種商品。
dp[i][j]指的是將前i種物品裝進(jìn)限重為j的背包可以獲得的最大價值
dp[i-1][j]指的是將前i-1種物品裝進(jìn)限重為j的背包可以獲得的最大價值
dp[i-1][j-w[i]+v[i]指的是將前i-1種物品裝進(jìn)限重為j的背包可以獲得的最大價值+將一個第i種物品裝入的總價值.
dp[i][j-w[i]+v[i]指的是將前i種物品裝進(jìn)限重為j的背包可以獲得的最大價值+將一個第i種物品裝入的總價值
也就是說，當(dāng)我們裝入第1個第i種物品后，假設(shè)讓dp[i][j]=dp[i][j-w[i]+v[i],接下來再次將第2個第i中國物品裝入，此時i不改變，改變的是j，也就是背包容量。
得到的dp狀態(tài)方程為：
現(xiàn)在我們對完全背包進(jìn)行滾動數(shù)組優(yōu)化
與01背包類似，同樣二維狀態(tài)數(shù)組可以優(yōu)化成1維狀態(tài)數(shù)組，不同的是這里的數(shù)組滾動方向只能是正向，因為這里的max的第二項是dp[i]，而不是01背包的dp[i-1],這里就需要覆蓋，而01背包是要避免覆蓋的。
分析一下：
例如在遞推dp[j]時應(yīng)按w[i]到W的順序，這樣才能保證推dp[j]時dp[j-w[i]]保存的是狀態(tài)dp[i,j-w[i]]的值
因為我們進(jìn)行操作的時候，是用一維數(shù)組dp同時存儲這一狀態(tài)和上一狀態(tài)的值的，從w[i]到W遞推也就是說從前往后將i-1狀態(tài)更新為i狀態(tài)。
當(dāng)推導(dǎo)到j(luò)時，j往后的是i-1狀態(tài)。而j之前的是i狀態(tài)。要符合優(yōu)化之前的狀態(tài)方程，所以01背包問題的優(yōu)化數(shù)組滾動方向必然是從后往前的，注意沒對第j項進(jìn)行賦值時，第j項也是i-1狀態(tài)，所以這樣顯然就符合了狀態(tài)方程，優(yōu)化如下：
核心代碼如下;
int[] dp = new int[W + 1]; for (int i = 0; i < N; i++) {// 滾動數(shù)組優(yōu)化 正序枚舉jfor (int j = w[i]; j <= W; j--) {dp[j] = Integer.max(dp[j], dp[j - w[i]] + v[i]);} }3、多重背包問題
問題描述：
一共有N種物品，從第i(i從1開始)種物品的數(shù)量為n[i],重量為w[i],價值為v[i].在總重量不超過背包承載上限W的情況下，能夠裝入背包的最大價值為多少？
分析：
從裝第i種物品出發(fā)，裝入第i種物品0件、1件、…n[i]件（并且要滿足不超過限重）
dp狀態(tài)方程為：
接下來進(jìn)行滾動數(shù)組優(yōu)化，將狀態(tài)數(shù)組的第1維度消除，同時注意應(yīng)該逆序操作，同樣的解釋思路，參見01背包。
核心代碼：
關(guān)于背包問題以及其他的優(yōu)化思路，這里不做擴(kuò)展。
3、參考
這些文章對我理解背包問題以及動態(tài)規(guī)劃有比較大的幫助：
1、滾動數(shù)組優(yōu)化
2、《滾動數(shù)組》—滾動數(shù)組思想，運用在動態(tài)規(guī)劃當(dāng)中
3、動態(tài)規(guī)劃之背包問題系列
4、九章算法 | 背包問題
5、怎樣學(xué)好動態(tài)規(guī)劃？
6、動態(tài)規(guī)劃算法3——最長上升子序列
7、我的知乎收藏
總結(jié)
以上是生活随笔為你收集整理的dp笔记：关于DP算法和滚动数组优化的思考的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： C++中的sort函数对二维数组排序是按
- 下一篇： 为什么最近都进不到拍卖行啊 有些人怎么就