什么是動態(tài)規(guī)劃：動態(tài)規(guī)劃_百度百科
內(nèi)容太多了不作介紹，重點(diǎn)部分是無后效性，重疊子問題，最優(yōu)子結(jié)構(gòu)。
問S->P1和S->P2有多少種路徑數(shù)，毫無疑問可以先從S開始深搜兩次，S->P1和S->P2找出所有路徑數(shù)，但是當(dāng)這個圖足夠大，那就會超時。
動態(tài)規(guī)劃旨在用空間換時間，我們可以發(fā)現(xiàn)S->P2的路上，實(shí)際上重復(fù)計(jì)算了S->P1，然后再去計(jì)算P1->P2，如果我們第一次計(jì)算S->P1的時候，保留了P1點(diǎn)的路徑數(shù)，那么就不用再次計(jì)算S->P1了。
無后效性：未來的狀態(tài)不會影響過去的狀態(tài)，如果我在P1->P2的時候，S->P1多了一條路出來，那么先前保留的路徑數(shù)就是錯誤的。
tip：下面的例題講解并不是特別好，還未修正，建議先拉到最下面看20230504 Update.
經(jīng)典的數(shù)塔問題也是dp算法的入門問題之一
假設(shè)你有這么一個數(shù)塔，你的目標(biāo)是求最底層到最高層，求出最大路徑和
比如3->7->2->9這個路徑，他的路徑和是3+7+2+9
不難發(fā)現(xiàn)如果要求到9的最大路徑和，首先要求出他前一層的最大路徑
核心代碼dp[i][j]=max(dp[i-1][j],dp[i-1][j+1])+a[i][j]
dp[i][j]（9的最大路徑和)
a[i][j]（9自己）
dp[i-1][j]（前一層5的最大路徑和）dp[i-1][j+1]（前一層2的最大路徑和）
在前一層的最大路徑和取大的那一個
例題：[NOIP2005 普及組] 采藥 - 洛谷
這道題輸入這么少也不用scanf了，直接上cin加上小優(yōu)化
inline void scan(){
ios::sync_with_stdio(false);//解除與scanf和cout的同步,具體體現(xiàn)在緩沖區(qū)
cin.tie(nullptr),cout.tie(nullptr);//可以加快一點(diǎn)速度
cin>>T>>m;
for(int i=1;i<=m;++i)
cin>>t[i]>>v[i];
}很明顯就是各個最優(yōu)子問題的問題，要取到最多的價值，必然前一個狀態(tài)也是最多的。
所以考慮定義問題的全部基礎(chǔ)屬性，每個草藥有價值和對應(yīng)所需的時間，目標(biāo)是最大價值。
作出以下定義
定義dp[i][j]為采前i朵，消耗時間j內(nèi)的最大價值
不難得出以下兩種情況
1.當(dāng)前時間可以采走這支草藥
(1)如果要采這支采藥,那先前狀態(tài)就要預(yù)留j-t[i]時間來滿足定義
(2)如果不采那最大價值就是先前狀態(tài)dp[i-1][j]
因?yàn)椴磺宄囊环N情況更好,但是我們只需要最大值,所以max
綜上dp[i][j]=max(dp[i-1][j],dp[i-1][j-t[i]]+v[i]);
2.當(dāng)前時間不夠采走這支草藥,采不了那就不采,繼承先前狀態(tài).
即dp[i][j]=d[i-1][j]
或者說延續(xù)用上文的想法,n支草藥價值最大我不知道
如果只有1支草藥呢?,那我是不是就知道了
1支草藥知道了,那我2支草藥是不是也知道了然后...直接從基礎(chǔ)狀態(tài)循環(huán)到結(jié)束，即從第一支草藥開始循環(huán)。
顯而易見不能從采最后幾朵開始往前判斷，前面狀態(tài)都不清楚，怎么可以從后面開始。
AC代碼文章來源：http://www.zghlxwxcb.cn/news/detail-439294.html
#include <bits/stdc++.h>
using namespace std;
int T,m,t[101],v[101],dp[101][1001];
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>T>>m;
for(int i=1;i<=m;++i)
cin>>t[i]>>v[i];
for(int i=1;i<=m;++i){
for(int j=1;j<=T;++j){
if(j>=t[i])dp[i][j]=max(dp[i-1][j],dp[i-1][j-t[i]]+v[i]);
else dp[i][j]=dp[i-1][j];
}
}
cout<<dp[m][T];
return 0;
}這道題還可以接著優(yōu)化,因?yàn)椴浑y發(fā)現(xiàn)dp[][]的一維空間始終是在dp[i]和dp[i-1]范圍內(nèi)
也就是說我們其實(shí)可以舍棄這一維來節(jié)約很大范圍的空間。
dp代碼
for(int i=1;i<=m;++i)
for(int j=T;j>=t[i];j--)
dp[j]=max(dp[j-t[i]]+v[i],dp[j]);內(nèi)部循環(huán)必須從大到小，因?yàn)橄惹笆菓?yīng)用了i-1先前狀態(tài)去得出i狀態(tài)，但是此處舍去了一維之后就會導(dǎo)致兩者狀態(tài)都會出現(xiàn)在這個小小的一維數(shù)組里面。
比如說用線段來表示所有情況，藍(lán)色的得出了紅色的狀態(tài)。
但是如果我只剩下了一條線段呢？
?如果中間被前面先修改了，那么后面要更新狀態(tài)的時候用的就是紅色，而不是我們所需要的藍(lán)色。
所以只能從后往前去推狀態(tài)才能保證我們所需要的一直是藍(lán)色，而不會被更新成紅色。
發(fā)現(xiàn)了吧，重點(diǎn)在于找出繼承狀態(tài)（遞推式），比如定義的是前n個人，而不是任意n個人，這樣n-1和n的區(qū)別就在于多了一個人，只要讓先前狀態(tài)抽出能滿足多一個人的情況，那就是后者的狀態(tài)。
例題：5 倍經(jīng)驗(yàn)日 - 洛谷
?和上面那道題基本沒有什么區(qū)別，定義所有相關(guān)的基礎(chǔ)態(tài)
定義dp[i][j]為前i個人 用j個藥 可以獲得的最大經(jīng)驗(yàn)值然后就可以得出遞推式
for(int i=1;i<=n;++i)
for(int j=1;j<=x;++j)
if(j>=use[i])
dp[i][j]=max(dp[i-1][j]+lose[i],dp[i-1][j-use[i]]+win[i]);
else
dp[i][j]=dp[i-1][j]+lose[i];
如果能打過,那么我可以選擇打或者不打
如果打不過,那只能不打但是這道題有一個注意點(diǎn)是，J可以從0開始，因?yàn)榇嬖诓挥盟幘涂梢源蜻^的情況，所以先初始化不用藥的情況。
初始化
for(int i=1;i<=n;++i)
if(use[i]==0)
dp[i][0]=dp[i-1][0]+win[i];
else
dp[i][0]=dp[i-1][0]+lose[i];AC代碼
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e3+1;
long long n,x,win[MAXN],lose[MAXN],use[MAXN],dp[MAXN][MAXN];
//dp[i][j]前i個人,使用j個藥,能獲得的最大經(jīng)驗(yàn)值
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>n>>x;
for(int i=1;i<=n;++i){
cin>>lose[i]>>win[i]>>use[i];
}
for(int i=1;i<=n;++i)
if(use[i]==0)
dp[i][0]=dp[i-1][0]+win[i];
else
dp[i][0]=dp[i-1][0]+lose[i];
for(int i=1;i<=n;++i)
for(int j=1;j<=x;++j)
if(j>=use[i])
dp[i][j]=max(dp[i-1][j]+lose[i],dp[i-1][j-use[i]]+win[i]);
else
dp[i][j]=dp[i-1][j]+lose[i];
cout<<dp[n][x]*5;
return 0;
}很明顯這道題i和i-1也是滾動使用的
不過n的范圍不是很大,所以不考慮優(yōu)化例題：瘋狂的采藥 - 洛谷
和上上題采藥的區(qū)別就是，每個藥可以無限采
每條線的含義都是一樣的，也就是每個藥都只能采一次。
這道題每個藥都可以無限采，也就是說同一行之間也要去迭代所有情況
上上題里面發(fā)現(xiàn)了，一維dp一定要逆序時間才能得出不迭代自己的狀態(tài)，那么這道題正序迭代即可。
AC代碼
#include <bits/stdc++.h>
using namespace std;
const int MAXM=1e4+1;
const int MAXT=1e7+1;
int T,m,t[MAXM],v[MAXM];
long long dp[MAXT];
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>T>>m;
for(int i=1;i<=m;++i){
cin>>t[i]>>v[i];
}
for(int i=1;i<=m;++i){
for(int j=t[i];j<=T;++j){
dp[j]= max(dp[j],dp[j-t[i]]+v[i]);
}
}
cout<<dp[T];
return 0;
}j一定要從t[i]開始，不然下標(biāo)要越界了。
如果要寫出二維dp首先要改變定義，因?yàn)橐粋€是只能用一次，一個是無限用，遞推式必然不一樣
定義dp[i][j]為采前i朵（無限采），消耗時間j內(nèi)的最大價值
不難得出以下兩種情況
1.當(dāng)前時間可以采走這支草藥
(1)繼承先前狀態(tài)
(2)迭代自己
綜上dp[i][j]=max(dp[i-1][j],dp[i][j-t[i]]+v[i]);
注意此處是i,不是i-1
2.當(dāng)前時間不夠采走這支草藥,采不了那就不采,繼承先前狀態(tài).
即dp[i][j]=d[i-1][j]20230504 Update.
在隱隱約約或者分析出當(dāng)前做的題目是dp題目的時候，dp題目的做法可以采取以下兩種方式。
第一種：
1. 分析題目，提取關(guān)鍵。
2. 用數(shù)學(xué)語言表達(dá)問題。
3. 定狀態(tài)轉(zhuǎn)移方程。
4. 初始化。
5. 循環(huán)求解。
第二種：
1. 直接分析答案可能和哪些屬性有關(guān)聯(lián)。
2. 定狀態(tài)轉(zhuǎn)移方程。
3. 初始化。
4. 循環(huán)求解。
如果能用第一種分析出來那肯定是最好的，有了數(shù)學(xué)公式干什么都方便。
看例題。
[NOIP2012 普及組] 擺花 - 洛谷
因?yàn)楸旧X蒻是蒟蒻（叉腰），所以直接用第二種方法。
可以發(fā)現(xiàn)擺花方案只和下面幾種屬性有關(guān)：
1. 花的種類
2. 花的數(shù)量，以及總數(shù)要小于一個限定數(shù) -> 花的總數(shù)
3. 花的順序
嘗試做出定義??為用上前??種花，且到當(dāng)前為止已經(jīng)用了??盆花的所有方案數(shù)。
當(dāng)我們正序迭代這個式子的時候，可以發(fā)現(xiàn) 3. 花的順序 這個屬性被隱含解決了。
即這個定義目前看來還是可行的。
根據(jù)定義易得：，其中??（不管他到現(xiàn)在最多能用多少，直接暴力枚舉）。
初始化則為一種花都不用，一盆花都沒有，即??。其中??。
出現(xiàn)了??所以循環(huán)的時候要注意下標(biāo)越界，判斷??。
AC代碼
#include <bits/stdc++.h>
using namespace std;
const int MOD=1e6+7,N=101;
int n,m,f[N][N],a[N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;++i)
cin>>a[i];
for(int i=0;i<=n;++i)
f[i][0]=1;
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
for(int k=j-a[i];k<=j;++k)
if(k>=0)f[i][j]=(f[i][j]+f[i-1][k])%MOD;
cout<<f[n][m];
return 0;
}例題：[NOIP2008 普及組] 傳球游戲 - 洛谷文章來源地址http://www.zghlxwxcb.cn/news/detail-439294.html
到了這里，關(guān)于★動態(tài)規(guī)劃（DP算法）詳解的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
