今天直接開(kāi)始講解

FIRST：如何抽象出動(dòng)態(tài)規(guī)劃算法？

這個(gè)問(wèn)題，困擾了無(wú)數(shù)代OIER，包括本蒟蒻

在比賽的時(shí)候，看一道題，怎么想到他是什么算法的呢？

這就需要抽象能力

而不同的算法，往往有著不同的特點(diǎn)

就來(lái)說(shuō)說(shuō)動(dòng)態(tài)規(guī)劃的題目特點(diǎn)

1. 通過(guò)遍歷，能夠把所有的情況考慮到。這一點(diǎn)同樣適合于遞歸

2. 有可能存在重疊性的子問(wèn)題。沒(méi)錯(cuò)，這一點(diǎn)也適用于遞歸

有的同學(xué)就問(wèn)了

那動(dòng)態(tài)規(guī)劃和遞歸不是同樣的特點(diǎn)嗎？

回到蒟蒻寫的動(dòng)態(tài)規(guī)劃1

里面說(shuō)過(guò)，動(dòng)態(tài)規(guī)劃是可以用遞歸代替的

也就是說(shuō)，如果你的狀態(tài)轉(zhuǎn)移方程真的實(shí)在絞盡腦汁費(fèi)勁九牛二虎之力也想不出來(lái)，就用遞歸來(lái)做

但代價(jià)就是也許拿不到滿分

SECOND：解題思路

動(dòng)態(tài)規(guī)劃抽象出狀態(tài)之后，就要進(jìn)行遍歷每一個(gè)狀態(tài)

1. 抽象狀態(tài)

2. 初始化

3. 確定循環(huán)起始以及邊界

4. 寫出狀態(tài)轉(zhuǎn)移方程

5. 輸出

6. return 0;

大概就是上述這個(gè)過(guò)程了

每日例題：

題目描述
辰辰是個(gè)天資聰穎的孩子，他的夢(mèng)想是成為世界上最偉大的醫(yī)師。為此，他想拜附近最有威望的醫(yī)師為師。醫(yī)師為了判斷他的資質(zhì)，給他出了一個(gè)難題。醫(yī)師把他帶到一個(gè)到處都是草藥的山洞里對(duì)他說(shuō)：“孩子，這個(gè)山洞里有一些不同的草藥，采每一株都需要一些時(shí)間，每一株也有它自身的價(jià)值。我會(huì)給你一段時(shí)間，在這段時(shí)間里，你可以采到一些草藥。如果你是一個(gè)聰明的孩子，你應(yīng)該可以讓采到的草藥的總價(jià)值最大?！?
如果你是辰辰，你能完成這個(gè)任務(wù)嗎？

輸入格式
第一行有 22 個(gè)整數(shù) ? T（1≤?≤10001≤ T≤1000）和 ? M（1≤?≤1001≤ M≤100），用一個(gè)空格隔開(kāi)，? T 代表總共能夠用來(lái)采藥的時(shí)間，? M 代表山洞里的草藥的數(shù)目。
接下來(lái)的 ? M 行每行包括兩個(gè)在 11 到 100100 之間（包括 11 和 100100）的整數(shù)，分別表示采摘某株草藥的時(shí)間和這株草藥的價(jià)值。
輸出格式
輸出在規(guī)定的時(shí)間內(nèi)可以采到的草藥的最大總價(jià)值。

輸入輸出樣例
輸入 #1復(fù)制
70 3 71 100 69 1 1 2
輸出 #1復(fù)制
3
說(shuō)明/提示
【數(shù)據(jù)范圍】
對(duì)于 30%30% 的數(shù)據(jù)，?≤10 M≤10；
對(duì)于全部的數(shù)據(jù)，?≤100 M≤100。

一個(gè)純純的01背包模板

1. 抽象狀態(tài)：f[i]表示第i分鐘采到的最大價(jià)值

2. 初始化：no

3. 確定循環(huán)起始以及邊界：第一層循環(huán)1到m，第二層循環(huán)t到0（真的是01背包模板，看不懂的可以借鑒一下上一篇文章）

4. 寫出狀態(tài)轉(zhuǎn)移方程：dp[j]=max(dp[j-w[i]]+val[i], dp[j]);如果采了這個(gè)藥，那么就要用當(dāng)前時(shí)間減去采藥的時(shí)間，也就是采藥之前需要的時(shí)間加上現(xiàn)在的狀態(tài)

5. 輸出（見(jiàn)代碼）

真正做題時(shí)，大家也可以按照這個(gè)順序，非常的清晰

那么有的同學(xué)就要問(wèn)了：狀態(tài)定義有什么規(guī)律嗎？

1. 首先，我們先創(chuàng)建一個(gè)數(shù)組，f數(shù)組，假設(shè)他是一維的，然后去想這個(gè)一維狀態(tài)表示什么（簡(jiǎn)單多了）

2. 就假設(shè)是一維，嘗試寫狀態(tài)轉(zhuǎn)移方程

3. 如果發(fā)現(xiàn)，寫不通了，也就是有更多的情況表示不出來(lái)

4. 增加維度

然后循環(huán)上述操作

但是遇到很難的題，還得是靠智商，因?yàn)殡y的動(dòng)態(tài)規(guī)劃不僅僅要抽象出來(lái)

更需要你優(yōu)化，也就是減少維度

來(lái)遲的AC代碼：

# include <iostream>
# include <cstdio>
using namespace std;
int w[105], val[105];
int dp[1005];
int main(){
    int t,m;    
    scanf("%d%d",&t,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&w[i],&val[i]);
    }
    for(int i=1;i<=m;i++) {
        for(int j=t;j>=0;j--) {
            if(j>=w[i]){
                dp[j]=max(dp[j-w[i]]+val[i], dp[j]);
            }
        }
    }    
    printf("%d",dp[t]);
    return 0;
}

---

這會(huì)動(dòng)態(tài)規(guī)劃系列就真的結(jié)束了

這次講算法比之前真的費(fèi)了更大的力氣，更多的時(shí)間，更多的鍵盤（）

所以希望各位佬能夠點(diǎn)個(gè)免費(fèi)的贊

如果動(dòng)態(tài)規(guī)劃方面還有什么不明白的，隨時(shí)私信我

我可以出番外篇（）

這篇文章到這里就結(jié)束了

再見(jiàn)文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-402900.html