Day 37

00. 動態規劃理論基礎

最常見的動態規劃題目其實就是 求最值，比如說股票問題、背包問題，都是在求使用怎樣的策略能使得整個系統達到一個最優化的狀態。

這是否和貪心比較類似呢？

其實貪心算法和動態規劃算法的區別還是比較大的，貪心算法每一次的最優解一定 包含 上一次的最優解，是局部的最優推出全局的最優，而動態規劃的最優解不一定包含前一次的最優解，而是有可能是由更前面的部分推出的，所以通常通過 dp[] 數組來將前面的所有最優解來保存下來。

動態規劃其實是一個 窮舉 的過程，得到最優解的前提就是要將所有的可能導致最優解的情況列出來，逐步推出最終的結果，而貪心更像是確定了一個路線，直接來走這個最優的路線，但這種最優通常是一種經驗性的，較難推導的方式，相信做過貪心部分的朋友應該深有體會，這也就導致貪心得到的可能不是最優解，但相對的時間復雜度較低，而動態規劃本質是窮舉就會導致其時間復雜度相對較高。

再來談談動態規劃和暴力解法的區別，比如說斐波那契數列，使用遞歸來求會導致大量的重復計算，所以考慮引入備忘錄，也就是記憶搜索的方法，記憶搜索的方法是自頂向下的，也就是要算 f(5) 要遞歸到 f(1) 才開始計算結果，而且由于遞歸的限制，思考其實可以采用自底向下的方式，從 f(1) 開始向上層遞歸，這其實就是動態規劃的方法。

01. 斐波那契數（No. 509）

題目鏈接

代碼隨想錄題解

<1> 題目

斐波那契數 （通常用 F(n) 表示）形成的序列稱為 斐波那契數列 。該數列由 0 和 1 開始，后面的每一項數字都是前面兩項數字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

給定 n ，請計算 F(n) 。

示例 1：

輸入：n = 2
輸出：1
解釋：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

輸入：n = 3
輸出：2
解釋：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

輸入：n = 4
輸出：3
解釋：F(4) = F(3) + F(2) = 2 + 1 = 3

提示：

• 0 <= n <= 30

<2> 筆記

這道題目相信大家都能比較容易的寫出來，這里以本題為案例看看動態規劃的一些小特點。

動態規劃比較重要的一個點就是 狀態，解題的關鍵在于能否列出正確的 狀態轉移方程，以及這個狀態轉移方程最終能否窮舉出問題的最終答案，其實這就要求這個算法問題具備 最優子結構；因為需要不斷用到前面的狀態來推導后面狀態的最優，這就會引出大量的重復的計算這也就是常說的 重疊子問題，所以使用暴力解法的效率很低。

這道斐波那契數列其實就很好的展示了重疊子問題，但其實并不存在重疊子問題，所以嚴格上并不算動態規劃的題目。

比如計算 f(5)，畫出遞歸樹

可以看出其實是計算了兩遍 f(3) 的，如果說計算的數字更大，子問題的個數會以指數級的速度增長，時間復雜度為 2ⁿ。這就是所謂的重疊子問題。

可以注意到 f(n) 的狀態其實是由 f(n - 1) 和 f(n - 2) 推導出來的，轉移的方式其實就是兩者加和，這樣其實就很容易看出 dp 數組的含義，就是 dp[n] = f(n)，狀態轉移公式也順帶推了出來（這就是本題較為簡單的原因），因為這幾步幾乎不用怎么思考。

直接寫出代碼。

<3> 代碼

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

02. 爬樓梯（No. 70）

題目鏈接

代碼隨想錄題解

<1> 題目

假設你正在爬樓梯。需要 n 階你才能到達樓頂。

每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？

示例 1：

輸入：n = 2
輸出：2
解釋：有兩種方法可以爬到樓頂。

1. 1 階 + 1 階
2. 2 階

示例 2：

輸入：n = 3
輸出：3
解釋：有三種方法可以爬到樓頂。

1. 1 階 + 1 階 + 1 階
2. 1 階 + 2 階
3. 2 階 + 1 階

提示：

• 1 <= n <= 45

<2> 筆記

本題其實也沒有引入太多的遞歸思想，其實可以看作是下一題 使用最小花費爬樓梯 的一個導入。

本題的 dp 定義其實是較為簡單的，因為要得出 n 階臺階由幾種走法，可以想到就是用 dp[n] 來代表共 n 階由多少種走法。

爬到第一層樓有一種方法，爬到第二層有兩種方法，那爬到第三層其實就有三種方法，一種是通過第一層跨兩步，另一種是第二層跨一步。

很多朋友做這道題的時候會有一個疑問的地方，就是我從第一層走一步再走一步算不算一種方法呢？或者說從第四層走兩次到第五層，這里想不通的朋友是因為沒有將目光放到全局，其實將這些方式寫出來得到的數列是相同的，比如 n = 3 的時候 1 1 1，可以理解成從 2 到 3 的一部分，也可以理解成從 1 跨兩步到 3，計算的話其實就計算其中的一部分即可，否則會出現沖突。

使用遞歸五步法來規范一下：

1. 確認 dp 的含義：爬到第i層樓梯，有dp[i]種方法
2. 確認遞推公式：dp[i] = dp[i - 1] + dp[i - 2]
3. dp 數組如何初始化：題目中說了n是一個正整數，所以 dp[0] 是沒有意義的，而遞歸推出后面的部分有需要兩個元素，所以初始化就初始化 dp[1] 和 dp[2]
4. 遞歸的遍歷順序：需要用到前面的元素，從前向后遍歷
5. 嘗試舉例推導

<3> 代碼

class Solution {public int climbStairs(int n) {if (n < 3) return n;int[] dp = new int[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];}
}

03. 使用最小花費爬樓梯（No. 746）

題目鏈接

代碼隨想錄題解

<1> 題目

給你一個整數數組 cost ，其中 cost[i] 是從樓梯第 i 個臺階向上爬需要支付的費用。一旦你支付此費用，即可選擇向上爬一個或者兩個臺階。

你可以選擇從下標為 0 或下標為 1 的臺階開始爬樓梯。

請你計算并返回達到樓梯頂部的最低花費。

示例 1：

輸入：cost = [10,15,20]
輸出：15
解釋：你將從下標為 1 的臺階開始。

• 支付 15 ，向上爬兩個臺階，到達樓梯頂部。
  總花費為 15 。

示例 2：

輸入：cost = [1,100,1,1,1,100,1,1,100,1]
輸出：6
解釋：你將從下標為 0 的臺階開始。

• 支付 1 ，向上爬兩個臺階，到達下標為 2 的臺階。
• 支付 1 ，向上爬兩個臺階，到達下標為 4 的臺階。
• 支付 1 ，向上爬兩個臺階，到達下標為 6 的臺階。
• 支付 1 ，向上爬一個臺階，到達下標為 7 的臺階。
• 支付 1 ，向上爬兩個臺階，到達下標為 9 的臺階。
• 支付 1 ，向上爬一個臺階，到達樓梯頂部。
  總花費為 6 。

提示：

• 2 <= cost.length <= 1000
• 0 <= cost[i] <= 999

<2> 筆記

有了上一道題的鋪墊其實本題就比較容易了，到達臺階 n 有兩種方式分別是從 n - 1 和 n - 2 到達，所以需要有一個數組來存儲之前的狀態。

1. 確定dp數組以及下標的含義，使用動態規劃，就要有一個數組來記錄狀態，本題只需要一個一維數組dp[i]就可以了，dp[i]的定義：到達第i臺階所花費的最少體力為dp[i]。
2. 確定遞推公式：dp[i - 1] 跳到 dp[i] 需要花費 dp[i - 1] + cost[i - 1]，dp[i - 2] 跳到 dp[i] 需要花費 dp[i - 2] + cost[i - 2]，那選擇哪個呢？一定是最小的，所以 dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
3. dp 數組如何初始化：和上面題目相同，只需要初始化兩個即可，也就是 dp[0] 和 dp[1]，分別初始化成 cost[0] 和 ocst[1]
4. 確定遍歷順序：和上題相同，都是自底向上，從前向后遍歷
5. 舉例推導，發現沒有問題

通過上面的梳理就能寫出代碼

<3> 代碼

class Solution {public int minCostClimbingStairs(int[] cost) {int n = cost.length;if (n < 2) {return 0;}int[] dp = new int[n + 1];dp[0] = 0;dp[1] = 0;for (int i = 2; i <= n; i++) {dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]); }return dp[n];}
}