目錄

動(dòng)態(tài)規(guī)劃理論基礎(chǔ)

什么是動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃的解題步驟

動(dòng)態(tài)規(guī)劃的debug

509. 斐波那契數(shù)

前言

思路

算法實(shí)現(xiàn)

方法一：動(dòng)態(tài)規(guī)劃

方法二：遞歸法

?70. 爬樓梯

前言

思路

算法實(shí)現(xiàn)

拓展

746. 使用最小花費(fèi)爬樓梯

算法實(shí)現(xiàn)

總結(jié)

---

動(dòng)態(tài)規(guī)劃理論基礎(chǔ)

什么是動(dòng)態(tài)規(guī)劃

????????動(dòng)態(tài)規(guī)劃，英文名為Dynamic Programming，簡(jiǎn)稱DP，如果某一問(wèn)題有很多重疊子問(wèn)題，使用動(dòng)態(tài)規(guī)劃是最有效的。所以動(dòng)態(tài)規(guī)劃中每一個(gè)狀態(tài)一定是由上一個(gè)狀態(tài)推導(dǎo)出來(lái)的，這一點(diǎn)就區(qū)分于貪心，貪心沒(méi)有狀態(tài)推導(dǎo)，而是從局部直接選最優(yōu)的。

動(dòng)態(tài)規(guī)劃的解題步驟

? ? ? ? 代碼隨想錄中總結(jié)了動(dòng)態(tài)規(guī)劃的五部曲：

1. 確定dp數(shù)組以及下標(biāo)的含義；
2. 確定遞推公式；文章鏈接
3. dp數(shù)組如何初始化；
4. 確定遍歷順序；
5. 舉例推導(dǎo)dp數(shù)組。

動(dòng)態(tài)規(guī)劃的debug

????????寫動(dòng)規(guī)題目，代碼出問(wèn)題很正常！找問(wèn)題的最好方式就是把dp數(shù)組打印出來(lái)，看看究竟是不是按照自己思路推導(dǎo)的！

????????做動(dòng)規(guī)的題目，寫代碼之前一定要把狀態(tài)轉(zhuǎn)移在dp數(shù)組的上具體情況模擬一遍，心中有數(shù)，確定最后推出的是想要的結(jié)果。然后再寫代碼，如果代碼沒(méi)通過(guò)就打印dp數(shù)組，看看是不是和自己預(yù)先推導(dǎo)的哪里不一樣。如果打印出來(lái)和自己預(yù)先模擬推導(dǎo)是一樣的，那么就是自己的遞歸公式、初始化或者遍歷順序有問(wèn)題了。如果和自己預(yù)先模擬推導(dǎo)的不一樣，那么就是代碼實(shí)現(xiàn)細(xì)節(jié)有問(wèn)題。

????????這樣才是一個(gè)完整的思考過(guò)程，而不是一旦代碼出問(wèn)題，就毫無(wú)頭緒的東改改西改改，最后過(guò)不了，或者說(shuō)是稀里糊涂的過(guò)了。

509. 斐波那契數(shù)

題目鏈接

文章鏈接

前言

?????????對(duì)于動(dòng)規(guī)，如果沒(méi)有方法論的話，可能簡(jiǎn)單題目可以順手一寫就過(guò)，難一點(diǎn)就不知道如何下手了。從一開(kāi)始做題就按照動(dòng)態(tài)規(guī)劃的五部曲順序來(lái)執(zhí)行。

思路

? ? ? ? 按照動(dòng)態(tài)規(guī)劃五部曲來(lái)執(zhí)行：

1. 確定dp數(shù)組以及下標(biāo)的含義：

? ? ? ? dp[i]的定義為：第i個(gè)數(shù)的斐波那契數(shù)列值是dp[i]；

? ? ?2.確定遞推公式：

? ? ? ? 題目中已經(jīng)給出遞推公式：dp[i] = dp[i - 1] + dp[i - 2]；

? ? ?3.dp數(shù)組初始化：

? ? ? ? 題目同樣已經(jīng)給出：dp[0] = 0, dp[1] = 1;

? ? ?4.確定遍歷順序：

? ? ? ? 前序遍歷；

? ? ?5.舉例推導(dǎo)dp數(shù)組：

????????按照這個(gè)遞推公式dp[i] = dp[i - 1] + dp[i - 2]，我們來(lái)推導(dǎo)一下，當(dāng)N為10的時(shí)候，dp數(shù)組應(yīng)該是如下的數(shù)列：0 1 1 2 3 5 8 13 21 34 55

????????如果代碼寫出來(lái)，發(fā)現(xiàn)結(jié)果不對(duì)，就把dp數(shù)組打印出來(lái)看看和我們推導(dǎo)的數(shù)列是不是一致的。

算法實(shí)現(xiàn)

方法一：動(dòng)態(tài)規(guī)劃

class Solution {
public:int fib(int n) {if (n <= 1) return n;vector<int> dp(n + 1);dp[0] = 0;dp[1] = 1;for (int i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
};

? ? ? ? 本題的dp實(shí)現(xiàn)很簡(jiǎn)單，因?yàn)轭}目信息已經(jīng)給出遞推公式和初始化值，也可以只維護(hù)dp數(shù)組前兩個(gè)值，算法如下：

class Solution {
public:int fib(int n) {if (n <= 1) return n;int dp[2];dp[0] = 0;dp[1] = 1;for (int i = 2; i <= n; i++) {int sum = dp[0] + dp[1];dp[0] = dp[1];dp[1] = sum;}return dp[1];}
};

方法二：遞歸法

? ? ? ? 還可以使用遞歸法進(jìn)行實(shí)現(xiàn)，遞歸的實(shí)現(xiàn)較為簡(jiǎn)單，遞歸終止條件就是當(dāng)n小于2。

class Solution {
public:int fib(int n) {if (n < 2) return n;return fib(n - 1) + fib(n - 2);}
};

?70. 爬樓梯

題目鏈接

文章鏈接

前言

? ? ? ? 本題就沒(méi)有像上一題一樣直接給出遞推公式，我們先自=自己舉幾個(gè)例子，就可以發(fā)現(xiàn)規(guī)律。

思路

? ? ? ? 按照題目條件爬到第一層樓梯有一種方法，爬到二層樓梯有兩種方法。那么第一層樓梯再跨兩步就到第三層 ，第二層樓梯再跨一步就到第三層。所以到第三層樓梯的狀態(tài)可以由第二層樓梯 和 到第一層樓梯狀態(tài)推導(dǎo)出來(lái)，那么就可以想到動(dòng)態(tài)規(guī)劃了。

? ? ? ? 利用動(dòng)態(tài)規(guī)劃五部曲來(lái)進(jìn)行分析：

1.確定dp數(shù)組以及下標(biāo)的含義：

? ? ? ? dp[i]的含義是爬到第i層樓梯，有dp[i]種方法；

2.確定遞推公式：

????????從dp[i]的定義可以看出，dp[i] 可以有兩個(gè)方向推出來(lái)：一個(gè)是dp[i - 1]，上i - 1層樓梯，已經(jīng)有dp[i - 1]種方法，再跳一個(gè)臺(tái)階就是dp[i]；另一個(gè)是dp[i - 2]，上i - 2層樓梯，已經(jīng)有dp[i - 2]種方法，那么再跳兩個(gè)臺(tái)階就是dp[i]。因此dp[i]就是 dp[i - 1]與dp[i - 2]之和！

????????所以dp[i] = dp[i - 1] + dp[i - 2] 。尤其注意在推導(dǎo)dp[i]的時(shí)候，一定要時(shí)刻想著dp[i]的定義，否則容易跑偏。這體現(xiàn)出確定dp數(shù)組以及下標(biāo)的含義的重要性！

3.dp數(shù)組初始化：

????????需要注意的是：題目中說(shuō)了n是一個(gè)正整數(shù)，題目根本就沒(méi)說(shuō)n有為0的情況。所以本題不需要討論dp[0]的初始化，直接初始化dp[1] = 1，dp[2] = 2，然后從i = 3開(kāi)始遞推。

4.確定遍歷順序：

????????從遞推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，遍歷順序一定是從前向后遍歷的；

5.舉例推導(dǎo)dp數(shù)組：

? ? ? ? 同上題思路一致。

算法實(shí)現(xiàn)

class Solution {
public:int climbStairs(int n) {if (n <= 1) return n;vector<int> dp(n + 1);dp[1] = 1;dp[2] = 2;for (int i = 3; i <= n; i++){dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
};

? ? ? ? 同樣也有簡(jiǎn)化算法，只維護(hù)dp數(shù)組前面幾個(gè)元素：

class Solution {
public:int climbStairs(int n) {if (n <= 1) return n;int dp[3];dp[1] = 1;dp[2] = 2;for (int i = 3; i <= n; i++){int sum = dp[1] + dp[2];dp[1] = dp[2];dp[2] = sum;}return dp[2];}
};

拓展

????????一步一個(gè)臺(tái)階，兩個(gè)臺(tái)階，三個(gè)臺(tái)階，直到 m個(gè)臺(tái)階，有多少種方法爬到n階樓頂？

class Solution {
public:int climbStairs(int n) {vector<int> dp(n + 1, 0);dp[0] = 1;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) { if (i - j >= 0) dp[i] += dp[i - j];}}return dp[n];}
};

746. 使用最小花費(fèi)爬樓梯

題目鏈接

文章鏈接

算法實(shí)現(xiàn)

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {vector<int> dp(cost.size() + 1);dp[0] = 0;dp[1] = 0;for (int i = 2; i <= cost.size(); i++) {dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);}return dp[cost.size()];}
};

? ? ? ? 簡(jiǎn)化之后：

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int dp[2];dp[0] = 0;dp[1] = 0;for (int i = 2; i <= cost.size(); i++) {int dpi = min(dp[0] + cost[i - 2], dp[1] + cost[i - 1]);dp[0] = dp[1];dp[1] = dpi;}return dp[1];}
};

總結(jié)

? ? ? ? 今天了解了動(dòng)態(tài)規(guī)劃的理論以及較簡(jiǎn)單題目的實(shí)現(xiàn)，在練習(xí)過(guò)程中熟悉了動(dòng)態(tài)規(guī)劃五部曲的使用，感覺(jué)非常實(shí)用！