目录
文档讲解：代码随想录
动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。
所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区别于贪心，贪心没有状态推导，而是从局部直接选最优的。
解题步骤：
确定dp数组（dp table）以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组
为什么要先确定递推公式，然后在考虑初始化呢？因为一些情况是递推公式决定了dp数组要如何初始化！
做动规的题目，写代码之前一定要把状态转移在dp数组上的具体情况模拟一遍，心中有数，确定最后推出的是想要的结果。然后再写代码，如果代码没通过就打印dp数组，看看是不是和自己预先推导的哪里不一样。
题目类型有：基础题目、背包问题、打家劫舍、股票问题、子序列问题 五大类
LeetCode 509. 斐波那契数
文档讲解：代码随想录
视频讲解：手把手带你入门动态规划 | LeetCode：509.斐波那契数_哔哩哔哩_bilibili
状态：简单题，做对了，要注意特殊情况的处理，怎么返回
class Solution:
def fib(self, n: int) -> int:
if n == 0: # 边界条件
return 0
if n == 1:
return 1
dp = [0]*(n+1) # step1：dp数组 dp[i]是第i个斐波那契数的值
dp[1] = 1 # step3：dp数组初始化
for i in range(2, n+1): # step4：因为要用到前面的状态，所以遍历顺序从前向后
dp[i] = dp[i-1] + dp[i-2] # step2：递推公式/状态转移方程
return dp[n]时间复杂度O(n)
空间复杂度O(n)
当前状态dp[i]只依赖前面两个状态dp[i-1]和dp[i-2]，所以可以不用维护一整个数组，而是3个量就可以了，得到上面程序的精简版：
class Solution:
def fib(self, n: int) -> int:
if n <= 1:
return n
dp = [0]*2
dp[1] = 1
for i in range(2, n+1):
sum = dp[0] + dp[1]
dp[0] = dp[1]
dp[1] = sum
return dp[1]时间复杂度O(n)
空间复杂度O(1)
70. 爬楼梯
文档讲解：代码随想录
视频讲解：
状态：去年7月11日做过，一周年了，结果还是不会做。 想dp数组的定义，想了好久，不确定到底该怎么定义，到底是第i走了几个台阶 or 一共走了多少台阶 or 剩下多少台阶，但最后需要返回的是方法数量，这该咋办呢？
我的错误思路：
# dp[i]是走完第i个台阶后，一共走了多少台阶
# 递推公式 dp[i] = dp[i-1] + 1或2
dp = [0] * n # 每次都走一个台阶，最多n步
dp[0] = 1 # 但也有可能是2?
if dp[-1] < n: # 该确定遍历顺序了，怎么遍历?
dp
正确思路是直接考虑每层楼梯的方法数目：
爬到第一层楼梯有一种方法，爬到二层楼梯有两种方法。
那么第一层楼梯再跨两步就到第三层 ，第二层楼梯再跨一步就到第三层。
所以到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来。
动规五部曲：
1. 一维数组 dp[i]： 爬到第i层楼梯，有dp[i]种方法
2. 递推公式：考虑最后一步走几个台阶，有两种情况1或者2。上i-1层楼梯，有dp[i - 1]种方法，那么再跳一个台阶就是dp[i]；上i-2层楼梯，有dp[i - 2]种方法，那么再一步跳两个台阶就是dp[i]。 所以爬到第i层楼梯，有dp[i] = dp[i - 1] + dp[i - 2] 种方法。
3. 初始化：从dp数组定义的角度出发，不用考虑dp[0]的初始化，直接dp[1] = 1，dp[2] = 2，然后从i = 3开始递推
4. 从前向后遍历
5. 举例推导dp数组 1 2 3 5 8 13
斐波那契数列：0、1、1、2、3、5、8、13、21、34……
与斐波那契数列后半截一样的
class Solution:
def climbStairs(self, n: int) -> int:
if n == 1:
return n
dp = [0]*(n+1) # 因为python下标从0开始，到n 长度为n+1
dp[1] = 1
dp[2] = 2
for i in range(3,n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
注意！一定要注意边界条件的处理！如果不写 if n==1: return n 的话，当n = 1时，dp[2] = 2 处就会报错list out of range。
空间和时间复杂度：O(n) 此题也可以像上一题一样优化空间复杂度为O(1)
拓展：这道题目还可以继续深化，就是一步一个台阶，两个台阶，三个台阶，直到 m个台阶，有多少种方法爬到n阶楼顶。这其实是一个完全背包问题，后面会讲。
746. 使用最小花费爬楼梯
文档讲解：代码随想录
视频讲解：
状态：自己做对了！类比上一题。
动规五部曲：
定义：dp[i]是到达第i个台阶需要支付的最少费用
公式：dp[i] = min((dp[i-1] + cost[i-1]), dp[i-2] + cost[i-2])
初始化：dp[0] = 0 dp[1] = 0 题目中说 “你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯” 也就是相当于 跳到 下标 0 或者 下标 1 是不花费体力的
顺序：从前向后
举例：
cost = [1,100,1,1,1,100,1,1,100,1]
下标 0 1 2 3 4 5 6 7 8 9 楼顶
dp数组 0 0 1 2 2 3 3 4 4 5 6 确定dp数组长度为len(cost)+1
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
dp = [0]*(len(cost)+1)
dp[0] = 0
dp[1] = 0
for i in range(2,len(cost)+1): # 从2开始推导
dp[i] = min((dp[i-1] + cost[i-1]), dp[i-2] + cost[i-2])
return dp[-1]感想
学习用时：晚上2h + 晚上2h