動(dòng)態(tài)規(guī)劃五部曲
動(dòng)態(tài)規(guī)劃，英文： Dynamic Programming, 簡(jiǎn)稱DP，如果某一個(gè)問題由很多重疊子問題，使用動(dòng)態(tài)規(guī)劃是最有效的。
所謂動(dòng)態(tài)規(guī)劃就是，在解決一個(gè)問題的過程中，將其分解為很多個(gè)小的部分，環(huán)環(huán)相扣。最典型的一個(gè)例子，我們?nèi)腴T編程時(shí)都學(xué)習(xí)過的斐波那契數(shù)，每個(gè)數(shù)都是由前面的兩個(gè)數(shù)字推導(dǎo)出來的，也就是所謂的前一個(gè)狀態(tài)。
動(dòng)態(tài)規(guī)劃解題步驟
在我剛接觸動(dòng)規(guī)題目的時(shí)候，比如說做01背包的問題，去把狀態(tài)轉(zhuǎn)移公式背下來，然后照著這樣去改改開始寫代碼，把題目做完之后可能都不知道后一個(gè)狀態(tài)是如何推導(dǎo)而來的。
對(duì)于動(dòng)態(tài)規(guī)劃的問題，如果我們?cè)诜治鲱}目的時(shí)候能夠看出來可以轉(zhuǎn)換為動(dòng)態(tài)規(guī)劃來求解的話一般就比較好解決了。對(duì)于此類問題我一般拆解為五步。簡(jiǎn)稱動(dòng)歸五部曲
1.確定dp數(shù)組 以及其下標(biāo)的含義
2.確定遞推公式
3.dp數(shù)組如何初始化
4.確定遍歷順序
5.舉例推導(dǎo)dp數(shù)組
在這里我給個(gè)建議，就是在做題的時(shí)候在我們把dp數(shù)組推導(dǎo)出來后，去將它打印出來，看看究竟是不是按照自己的思路推導(dǎo)的！就算出現(xiàn)問題的時(shí)候我們也可以很直觀的看出來問題出在哪里，當(dāng)出現(xiàn)錯(cuò)誤的時(shí)候不要去胡亂的修改，先去分析以上的五步到底是哪里出了問題，有沒有真正理解dp數(shù)組的含義。
實(shí)戰(zhàn)演練
-
爬樓梯
如果沒有接觸過的話乍一看會(huì)感覺沒有思路，既然每次只能爬1或2層臺(tái)階，爬到第一層樓有一種方法，爬到第二層樓就是有兩種方法（直接爬兩層或者分為兩次一次爬一層），如何與動(dòng)態(tài)規(guī)劃結(jié)合起來呢，既然一次只能爬1或2層，那么不管是哪層樓，是不是只能由它的前一層或前兩層爬過來。
分析到這里我們按照前面講的動(dòng)歸五部曲：
1.確定dp數(shù)組以及下標(biāo)的含義
dp[i]就是爬到第i層樓有dp[i]種方法
2.確定遞推公式
不管哪一層樓都只能由它的前一層或前兩層爬過來，那么很簡(jiǎn)單
dp[i] = dp[i-1]+dp[i-2].
在推導(dǎo)的時(shí)候，要時(shí)刻想著dp[i]的含義。
3.dp數(shù)組如何初始化
dp[i]的含義是爬到第i層樓，有dp[i]種方法。那么本題中我們應(yīng)該從哪里開始遍歷呢，dp[0]有沒有含義呢，很明顯的就可以得到dp[1] = 1;dp[2] = 2 那么根據(jù)狀態(tài)轉(zhuǎn)移方程，是不是要將dp[0]初始化為1呢，這顯然是不正確的。因?yàn)槲覀兂跏紶顟B(tài)就是在第0層，也就是說dp[0]是沒有意義的，所以在這道題中 應(yīng)該初始化dp[1] = 1,dp[2] = 2.
4.遍歷順序
我們已經(jīng)將dp[1]和dp[2]初始化后，那么就是從第三層樓開始遍歷，一直推導(dǎo)到我們所需要求的樓層。
5.舉例推導(dǎo)dp數(shù)組
前面我們已經(jīng)說了，在推導(dǎo)過程中將每一個(gè)狀態(tài)都打印出來，我們可以舉例推導(dǎo)dp[3] = 3,都是符合的，所以本題到這里按照五部曲已經(jīng)解決。當(dāng)我們熟悉了這個(gè)過程之后是非常快的。文章來源：http://www.zghlxwxcb.cn/news/detail-857871.html
class Solution {
public:
? ?int climbStairs(int n) {
? ? ? ?//1. 確定dp數(shù)組的含義 dp[i] 表示爬到第i層樓一共有多少種方法
? ? ? ?//2. 確定遞推公式 dp[i] = dp[i-1] + dp[i-2];
? ? ? ?//3. dp數(shù)組初始化 dp[1] = 1, dp[2] = 2
? ? ? ?//4. 遍歷順序 從第3層樓開始遍歷
? ? ? ?//5. 舉例推導(dǎo)驗(yàn)證
? ? ? ?vector<int> dp(n+1);
? ? ? ?if(n<=1) return n;
? ? ? ?dp[1] = 1,dp[2] = 2;
? ? ? ?for(int i= 3;i<=n;i++ )
? ? ? {
? ? ? ? ? ?dp[i] = dp[i-1]+dp[i-2];
? ? ? } ?
? ? ? ?return dp[n];
? ? ? ?
?
? }
};
以上就是對(duì)于動(dòng)態(tài)規(guī)劃問題的基本階梯思路 后續(xù)還會(huì)在本帖中更新相關(guān)動(dòng)態(tài)規(guī)劃問題的題解。文章來源地址http://www.zghlxwxcb.cn/news/detail-857871.html
到了這里，關(guān)于一文讀懂動(dòng)態(tài)規(guī)劃問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
