動態規劃

前言

在競賽中，如果遇到動態規劃的題目，只要不是經典題型，那么大概率就是以壓軸題的形式出現

用動態規劃解決問題的步驟:(遞推形式)

1.定義狀態表示:

根據經驗+需要的意義，賦予dp數組相應的含義

（主要還是看需要記什么）

2.推導狀態轉移方程:

在dp表中分析，當前格子如何通過其余格子推導出來的

3.初始化:

將顯而易見的以及邊界情況下的位置填上值，來讓后續填表的結果是正確的

4.確定填表順序:

根據狀態轉移方程，確定按照什么順序來填表

5.找出最終結果:

在表中找出需要的最終結果

洛谷 P10250 [GESP樣題 六級] 下樓梯
洛谷 P1216 [USACO1.5] [IOI1994]數字三?形 Number Triangles

動態規劃常要空間優化:
即把不用了的值給不要了
但是背包問題如果不能用1個數組優化，而要多個數組的話，那就不空間優化了，否則可能會超時
常見的優化方法:
方法一：一維轉幾個數
例題:洛谷   P10250 [GESP樣題 六級] 下樓梯方法二：二維轉一維
1.是否需要修改遍歷順序
2.刪掉一維即可
例題:洛谷  P1216 [USACO1.5] [IOI1994]數字三?形 Number Triangles

洛谷 P1115 最??段和
洛谷 P1541 [NOIP2010 提?組] 烏?棋

一些技巧:
1.狀態表示:
a.研究子數組或子序列問題時，從某個位置結尾來定義狀態表示 例:洛谷 P1115 最??段和
b.優化問題:有一維可以由其他維的數據推出的話，可以不要這一維(不是指那個空間優化方法)例題:洛谷  P1541 [NOIP2010 提?組] 烏?棋2.狀態轉移方程:
a.求方案數一般是相加
b.常從最后一步開始分析去推導狀態轉移方程3.初始化:
在求方案數時，一般將第一個位置初始化為1，其他位置為0

線性dp

特點：狀態轉移只依賴于前一個或前幾個狀態；狀態之間的關系是線性的

路徑類dp

洛谷 P1004 [NOIP2000 提?組] ?格取數

走兩次的得到的值之和最大問題:
（兩次的規則要一樣，走到不同位置的得到的值不一樣，且每位置的值只能得一次）
例題:洛谷  P1004 [NOIP2000 提?組] ?格取數
在狀態表示時：兩者如果是同時出發的(非同步則要改一點)，其橫縱坐標之和會是一個定值
一般表示為f[st][i1][i2]:
意思是：第一條路在[i1,st-i1]，第二條路在[i2,st-i2]時，兩者的路徑（取數）之和最大

經典線性dp

經典線性dp問題有兩個:最長上升子序列和最長公共子序列

這兩道題的解題思路，定義狀態表示方式和推導狀態轉移方程的技巧常被用到其他題目中去

洛谷 B3637 最?上升?序列
洛谷 P1091 [NOIP2004 提?組] 合唱隊形

最長上升子序列(數據范圍小時用此)
時間復雜度是O(n平方)
鏈接：洛谷  B3637 最?上升?序列
要理解最長上升子序列是什么意思！！！
1.狀態表示:
dp[i]表示:以i位置為結尾的所有子序列中，最長遞增子序列的長度
2.狀態轉移方程:
根據子序列的構成方式進行分類討論:第一種:子序列長度為1:此時的dp[i] = 1;
第二種: 子序列的長度大于1:設j為前面某一個數的下標
只要a[j]<a[i]，i位置元素跟在j元素后面就可以形成遞增序列
其dp[i] = max(dp[j]+1p,dp[i])
3.初始化:
每次填表的時候，先把這個位置的數改成最小的域值即可主要部分的代碼展示:
int ret = 0;
for(int i=1;i<=n;i++)
{ 
dp[i]=1;
for(int j=1;j<i;j++){if(a[j]<a[i])dp[i] = max(dp[i],dp[j]+1); }ret = max(ret,dp[i])
}應用: 洛谷  P1091 [NOIP2004 提?組] 合唱隊形

牛客網 【模板】最?上升?序列

最長上升子序列(數據范圍大時用此）
時間復雜度時O(n*logn)
鏈接:牛客網 【模板】最?上升?序列
優化動態規劃:
1.發現在考慮最長遞增子序列長度時，只用關心現在長度和序列最后一個元素
因此僅需統計長度為x的所有遞增序列中最后一個元素的最小值(創建數組去統計)
2.在統計過程中發現:
數組中的數呈現遞增趨勢，因為可以使用二分來查找插入位置
主要部分的代碼展示:
for(int i =1;i<=n;i++)
{//處理邊界情況if(len ==0||a[i]>f[len]) f[++len]=a[i];
else{//二分插入位置int l = 1,r = len;while(l<r){int mid = (l+r)/2;if(f[mid]>=a[i]) r = mid;else l =mid+1;}f[l] = a[i]} }

牛客網 ?可樂和最?公共?序列
洛谷 P2758 編輯距離

牛可樂和最長公共子序列
鏈接:牛客網  ?可樂和最?公共?序列
1.狀態表示:
dp[i][j]表示:
s1的[1,i]區間以及s2的[1,j]區間內的所有的子序列中，最長公共子序列的長度2.狀態轉移方程:
對于dp[i][j]，我們可以根據s1[i]與s2[j]的字符分情況討論：
第一種:兩個字符相同 dp[i][j] = dp[i-1][j-1]+1
第二種:兩個字符不同 有以下三種策略
a.去s1的[1,i-1]以及s2的[1,j]區間內找:此時最大長度為dp[i-1][j]
b.去s1的[1,i]以及s2的[1,j-1]區間內找:此時最大長度為dp[i][j-1]
c.去s1的[1,i-1]以及s2的[1,j-1]區間內找:此時最大長度為dp[i-1][j-1]
(發現c包含在a和b情況里)
然后要a,b中的最大值即可代碼展示:
for(int i =1;i<=n;i++)
{for(int j = 1;j<=m;j++){if(s[i-1] == t[j-1])f[i][j] = f[i-1][j-1]+1;else f[i][j] = max(f[i-1],f[i][j-1])}}應用:洛谷  P2758 編輯距離

背包問題分類

01背包問題:沒中物品只能選或不選（選0次或1次）

完全背包問題:每種物品可以選擇無限次

多重背包問題:每種物品有數量限制

分治背包問題:物品被分為若干組，每組只能選一個物品

混合背包:以上四種背包問題混在一起

多維費用的背包問題:限定條件不止有體積，還會有其他因素(比如重量)

背包問題的三種限定情況:
1.體積不超過j－>小于等于j->j>=v[i]
2.體積正好為j->恰好等于j->要判斷f表中某些狀態是否合法
3.體積至少為j->大于等于j->j<v[i]也是合法的，映射到0位置即可背包問題在求方案數時，要把不選的情況單獨寫出，然后從只選一個開始，不然套模板可能會錯
例:洛谷  P1077 [NOIP2012 普及組] 擺花

洛谷 P1077 [NOIP2012 普及組] 擺花

01背包問題

牛客網 【模板】01背包
洛谷 P2946 [USACO09MAR] Cow Frisbee Team S

01背包中的最大價值問題:
模板題:牛客網 【模板】01背包
v[i]表示第i個的體積   w[i]表示第i個的價值
第一問:求這個背包至多能裝多大價值的物品1.狀態表示:
dp[i][j]表示:從前i個物品中挑選，總體積不超過j，所有的選法中，能挑選出來的最大價值
那么dp[n][v]就是我們要的結果
2.狀態轉移方程:
dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i])
3.初始化:無
4.填表順序:從上往下(二維一般都是從上往下)  從右往左代碼表現:
for(int i = 1;i<=n;i++)
{ for(int j=0;j<=m;j++){f[i][j] = f[i-1][j];if(j>=v[i])f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);}
}
空間優化版:(熟練了之后，直接寫此)for(int i = 1;i<=n;i++)
{ for(int j=m;j>=v[i];j--)//01背包空間優化要修改遍歷順序{f[j] = max(f[j],f[j-v[i]]+w[i]);}
}第二問:
若背包恰好裝滿，求至少能裝多大價值
僅需要在第一問基礎上修改一下初始化以及最終結果即可
1.初始化
把所有位置先設置成-0x3f3f3f3f；然后把dp[0][0]修改成0
2.最終結果
要多一步判斷最后一個位置是不是小于0代碼展現:
memset(f,-0x3f,sizeof f);//多了這個
for(int i = 1;i<=n;i++)
{ for(int j=0;j<=m;j++){f[i][j] = f[i-1][j];if(j>=v[i])f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);}
}
if(f[n][m]<0)cout<<0<<endl;//多了這個
else cout << f[n][m]<<endl;//多了這個
空間優化版:(熟練了之后，直接寫此)
memset(f,-0x3f,sizeof f);for(int i = 1;i<=n;i++)
{ for(int j=m;j>=v[i];j--)//01背包空間優化要修改遍歷順序{f[j] = max(f[j],f[j-v[i]]+w[i]);}
}
if(f[m]<0)cout<<0<<endl;
else cout << f[m]<<endl;注意:有些題可能不能用這種空間優化,因為要用到之前的數據的多少不同了
例題:洛谷  P2946 [USACO09MAR] Cow Frisbee Team S
(這題還要注意的是狀態表示不能搞能力值總和為j，要搞總和模之后為j，不然空間時間都易超)

洛谷 P1164 ?A點菜

01背包中的方案數問題:
題目鏈接:洛谷  P1164 ?A點菜
1.狀態表示:
dp[i][j]表示:從前i個菜中挑選,總價錢恰好等于j,此時的總方案數
2.針對于a[i]選或不選，分兩種情況討論:
得:dp[i][j] = d[i-1][j]+d[i-1][j-a[i]]
注意第二個狀態可能不存在，要注意判斷一下j>=a[i]
3.初始化:
dp[0][0] = 1

完全背包問題

牛客網 【模板】完全背包

模板題:牛客網 【模板】完全背包
第一問:求這個背包至多能裝多大價值的物品
1.狀態表示:和01背包一樣
2.狀態轉移方程:
dp[i][j] = max(dp[i-1][j],dp[i][j-v[i]]+w[i])
3.初始化:
從第二行開始存，第一行全初始化為0
4.沒有空間優化時，是從上往下，從左往右第二問:若背包恰好裝滿，求至多能裝多大價值的物品
改法跟01背包那里完全相同與01背包的不同點:在空間優化時，完全背包的遍歷順序還是從左往右

多重背包

牛客網 多重背包

例題： 牛客網  多重背包
小tip:不是所有的多重背包問題都能用二進制優化，而且優化版本的代碼很長如果時間復雜度允許的情況下，能不優化就不優化
解法一:
1.狀態表示:
dp[i][j]表示:
從前i個物品中挑選，總重量不超過j的情況下，最大的價值2.狀態轉移方程:
這里不能用完全背包的方式(不是指那個空間優化)去優化
只能硬分x[i]+1種情況(選0個到選x[i]個)
選x[i]個:價值為dp[i-1][j-x[i]*w[i]]+x[i]*v[i] 3.初始化:
全部初始化為04.填表順序:
從上往下，從左往右
空間優化之后則是從右往左代碼展現:
for(int i =1;i<=n;i++)for(int j= m;j>=0;j--)for(int k = 0;k<=x[i]&&k*w[i]<=j;k++)f[j] = max(f[j],f[j-k*w[i]]+k*v[i])解法二:轉化為01背包問題
優化方式:用二進制將同種的x[i]個物品分組
(如果是求方案數的話，是不能用二進制去優化的，會多算幾種)
把這x[i]個物品拆成一些二進制數再加上多出來的數此題的有100種不同物品的話
如果同種的物品最多能分成5份，則數組的N要取(100+10)*5//+10純屬個人習慣

洛谷 P1077 [NOIP2012 普及組] 擺花

多重背包的方案數問題:
例題:洛谷  P1077 [NOIP2012 普及組] 擺花
也就狀態轉移方程和初始化改了一下

分組背包問題

洛谷 P1757 通天之分組背包

例題:洛谷  P1757 通天之分組背包
1.狀態表示:
dp[i][j]表示從前i組中挑選物品，總重量不超過j的情況下，最大的價值2.狀態轉移方程:
根據第i組選什么物品，可以分若干情況討論
這個在空間優化時，第二維也要從右到左

混合背包問題

洛谷 P1833 櫻花

例題:洛谷 P1833 櫻花
這個混合背包的話，分情況討論是哪種背包就是
注意的點是:多重背包和01背包的代碼具有可合并性

多維費用的背包問題

洛谷 P1910 L 國的戰?之間諜

例題:洛谷  P1910 L 國的戰?之間諜
這無非就是多加幾維就行
eg:
狀態表示:
dp[i][j][k]表示:
從前i個人中挑選，偽裝能力不超過j，總工資不超過k，此時能獲取到的最多資料總數
eg:像這種獲取到的最多資料總數，能砍到的最多的樹木這種一般不為限制條件，一般是所求的值
在空間優化時，也只能優化掉第一維(從前i個人中挑選--這個一般放第一維)
空間優化后，除了第一維的遍歷順序可能都需要發生變化

區間dp

區間dp是用區間的左右端點來描述狀態，通過小區間的解來推導出大區間的解

核心思想:將大區間劃分為小區間，其狀態轉移方程通常依賴于區間的劃分點

常見的劃分點的方式有兩個:

1.基于區間的左右端點，分情況討論

2.基于區間上的某一個點，劃分成左右區間討論

應用：在序列中只關心左右兩端，大概率用區間dp

洛谷 P1435 [IOI2000] 回?字串

例題:洛谷  P1435 [IOI2000] 回?字串
1.狀態表示:
dp[i][j]表示:
字符串[i,j]區間，變成回文串的最小插入次數
那么,dp[1][n]就是我們要的結果2.狀態轉移方程:
根據區間的左右端點，分情況討論對于區間dp的填表順序，一般用的是:
第一維循環:從小到大枚舉區間長度len;第二維循環:枚舉區間左端點i,然后計算出區間右端點j
j = i+len-1 
這個len有時從1開始，有時從2開始，看題
eg:
for(int len = 1;len<=n;len++)for(int i = 1; i+len-1<=n;i++)

洛谷 P2858 [USACO06FEB] Treats for the Cows G/S
洛谷 P3146 [USACO16OPEN] 248 G

關于這里的狀態轉移方程:
1.如果劃分點是基于區間的左右端點，分情況討論
eg: 洛谷  P2858 [USACO06FEB] Treats for the Cows G/S先拿左邊，然后去[i + 1, j] 區間獲得最多的錢，
即a[i] × (n ? len + 1) + dp[i + 1][j] 先拿右邊，然后去[i,j-1]區間獲得最多的錢
即a[j]*(n-len+1)+de[i][j-1]2.如果劃分點是基于區間上的某一個點，劃分成左右區間討論
eg: 洛谷    P3146 [USACO16OPEN] 248 G根據最后一次合并的情況，可以把區間分成[i,k][k+1,j](劃分點是k)