---

一、什么是動態(tài)規(guī)劃

動態(tài)規(guī)劃，英文：Dynamic Programming，簡稱DP，如果某一問題有很多重疊子問題，使用動態(tài)規(guī)劃是最有效的。

所以動態(tài)規(guī)劃中每一個狀態(tài)一定是由上一個狀態(tài)推導(dǎo)出來的

二、動態(tài)規(guī)劃的解題步驟

對于動態(tài)規(guī)劃問題，我將拆解為如下五步曲，這五步都搞清楚了，才能說把動態(tài)規(guī)劃真的掌握了！
確定dp數(shù)組（dp table）以及下標的含義
確定遞推公式
dp數(shù)組如何初始化
確定遍歷順序
舉例推導(dǎo)dp數(shù)組

三、509. 斐波那契數(shù)

1、動規(guī)五部曲：

這里我們要用一個一維dp數(shù)組來保存遞歸的結(jié)果
1、確定dp數(shù)組以及下標的含義
dp[i]的定義為：第i個數(shù)的斐波那契數(shù)值是dp[i]

2、確定遞推公式
為什么這是一道非常簡單的入門題目呢？
因為題目已經(jīng)把遞推公式直接給我們了：狀態(tài)轉(zhuǎn)移方程 dp[i] = dp[i - 1] + dp[i - 2];

3、dp數(shù)組如何初始化
題目中把如何初始化也直接給我們了，如下：

dp[0] = 0;
dp[1] = 1;
4、確定遍歷順序
從遞歸公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依賴 dp[i - 1] 和 dp[i - 2]，那么遍歷的順序一定是從前到后遍歷的

class S509:def func(self, n):# 1、創(chuàng)建dp數(shù)組，dp[i]:表示第i個數(shù)是第i個斐波那契數(shù)列dp = [0] * (n+1)# 3、初始化數(shù)組狀態(tài)dp[0] = 0dp[1] = 1# 4、確定遍歷順序for i in range(2, n+1):# 2、確定遞推公式dp[i] = dp[i - 1] + dp[i - 2]print(dp)return dp[n]r = S509()
n = 4
print(r.func(n))

四、70. 爬樓梯

簡單
假設(shè)你正在爬樓梯。需要 n 階你才能到達樓頂。
每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？

1、動規(guī)五部曲：

1、確定dp數(shù)組以及下標的含義
dp[i]： 爬到第i層樓梯，有dp[i]種方法

2、確定遞推公式
如何可以推出dp[i]呢？
從dp[i]的定義可以看出，dp[i] 可以有兩個方向推出來。
首先是dp[i - 1]，上i-1層樓梯，有dp[i - 1]種方法，那么再一步跳一個臺階不就是dp[i]了么。
還有就是dp[i - 2]，上i-2層樓梯，有dp[i - 2]種方法，那么再一步跳兩個臺階不就是dp[i]了么。
那么dp[i]就是 dp[i - 1]與dp[i - 2]之和！
所以dp[i] = dp[i - 1] + dp[i - 2] 。
在推導(dǎo)dp[i]的時候，一定要時刻想著dp[i]的定義，否則容易跑偏。
這體現(xiàn)出確定dp數(shù)組以及下標的含義的重要性！
3、dp數(shù)組如何初始化
不考慮dp[0]如何初始化，只初始化dp[1] = 1，dp[2] = 2，然后從i = 3開始遞推，這樣才符合dp[i]的定義。
4、確定遍歷順序
從遞推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，遍歷順序一定是從前向后遍歷的

class S70:def func(self, n):if n <= 1:return n# 1、創(chuàng)建dp數(shù)組，dp[i]:走到i臺階，一共用dp[i]種方法dp = [0] * (n + 1)# 3、數(shù)組初始化dp[1] = 1dp[2] = 2# 4、確定遍歷順序for i in range(3, n + 1):# 2、確定遞推公式dp[i] = dp[i - 1] + dp[i - 2]print(dp)return dp[n]r = S70()
n = 4
print(r.func(n))

五、746. 使用最小花費爬樓梯

簡單
給你一個整數(shù)數(shù)組 cost ，其中 cost[i] 是從樓梯第 i 個臺階向上爬需要支付的費用。一旦你支付此費用，即可選擇向上爬一個或者兩個臺階。
你可以選擇從下標為 0 或下標為 1 的臺階開始爬樓梯。
請你計算并返回達到樓梯頂部的最低花費。

1、動規(guī)五部曲：

1、確定dp數(shù)組以及下標的含義
使用動態(tài)規(guī)劃，就要有一個數(shù)組來記錄狀態(tài)，本題只需要一個一維數(shù)組dp[i]就可以了。
dp[i]的定義：到達第i臺階所花費的最少體力為dp[i]。

2、確定遞推公式
可以有兩個途徑得到dp[i]，一個是dp[i-1] 一個是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 - 1]跳還是從dp[i - 2]跳呢？
一定是選最小的，所以dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
3、dp數(shù)組如何初始化
看一下遞歸公式，dp[i]由dp[i - 1]，dp[i - 2]推出，既然初始化所有的dp[i]是不可能的，那么只初始化dp[0]和dp[1]就夠了，其他的最終都是dp[0]dp[1]推出。
新題目描述中明確說了 “你可以選擇從下標為 0 或下標為 1 的臺階開始爬樓梯?！?也就是說 到達 第 0 個臺階是不花費的，但從 第0 個臺階 往上跳的話，需要花費 cost[0]。
所以初始化 dp[0] = 0，dp[1] = 0;

4、確定遍歷順序
最后一步，遞歸公式有了，初始化有了，如何遍歷呢？
因為是模擬臺階，而且dp[i]由dp[i-1]dp[i-2]推出，所以是從前到后遍歷cost數(shù)組就可以了。

class S746:def func(self, cost):# 1、創(chuàng)建dp數(shù)組，dp[i]:走到樓梯i，需要最小的花費為dp[i]dp = [0] * (len(cost) + 1)# 3、初始化數(shù)組dp[0] = 0  # 你可以選擇從下標為 0 或下標為 1 的臺階開始爬樓梯。dp[1] = 0  # 你可以選擇從下標為 0 或下標為 1 的臺階開始爬樓梯。# 4、確定遍歷順序for i in range(2, len(cost) + 1):# 2、遞推公式# 在第i步，可以選擇從前一步（i-1）花費體力到達當前步，或者從前兩步（i-2）花費體力到達當前步# 選擇其中花費體力較小的路徑，加上當前步的花費，更新dp數(shù)組dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])return dp[len(cost)]r = S746()
cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
print(r.func(cost))

---