DP问题类型：

动态规划比较重要的是找到前后两个状态之间的联系，在向后遍历的过程中注意遍历的顺序和初始化操作。
动归基础类问题
背包问题
打家劫舍
股票问题
子序列问题

DP问题的一些注意事项：

动态规划类的问题代码都是比较简洁的，按照dp打印逻辑观察打印出来的数值。

1. dp数组以及下标的含义dp[i][j]，dp[i]
2. 递推公式
3. dp数组的初始化，有时候初始化成1，有时候初始化成0，有时候从某个下标开始初始化成1
4. 遍历顺序：两层for循环的顺序是怎样的
5. 打印dp数组：纠正动态规划的问题

509. 斐波那契数

复习动归五部曲：
dp数组-初始化-递推公式-遍历顺序-打印dp数组
入门级别的问题

class Solution:def fib(self, n: int) -> int:# 递归解法def r(n):if n == 0 : return 0if n == 1 : return 1return r(n-1) + r(n-2)return r(n)'''# 动态规划方法dp = [0] * (n+1)if n == 0 : return 0if n == 1 : return 1dp[0] = 0dp[1] = 1for i in range(2,n+1):dp[i] = dp[i-1] + dp[i-2]return dp[-1]'''''' # 一般方法if n == 0: return 0if n == 1: return 1cur = 1pre = 0i = 2while i<=n:temp = curcur = pre + curpre = tempi += 1return cur'''

70. 爬楼梯

核心思路： 第i个台阶收到前1个台阶和倒数第二个台阶影响
问题的思考方式是先那几个进行举例，然后找到其中的规律。三阶可以用一阶和二阶楼梯进行推导。
dp五部曲进行思考：

1. 确定dp[i]含义：第i个台阶的上楼的种类
2. 递推公式：dp[i] = dp[i-1] + dp[i-2]
3. 数组的初始化：dp[0] = 0 dp[1] = 1
4. 遍历方式：从前往后
5. 打印dp数组

class Solution:def climbStairs(self, n: int) -> int:# 当前楼梯走几步受到之前两个台阶的影响。# 根据dp五部曲进行求解dp = [0] * (n+1)if n == 0: return 0if n == 1: return 1dp[0] = 1dp[1] = 1for i in range(2,n+1):dp[i] = dp[i-1] + dp[i-2]return dp[n]

746. 使用最小花费爬楼梯

有两个数组cost[i]，当前台阶的花费受到前两个台阶花费的影响。
dp五步曲进行思考：

1. dp[i]含义：第i个台阶的最小花费
2. 递推公式：dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
3. dp数组的初始化：dp[0] = 0,dp[1] = 0
4. 遍历方式：从前往后
5. 打印dp数组

class Solution:def minCostClimbingStairs(self, cost: List[int]) -> int:dp = [0]*(len(cost)+1)if len(cost) <=1 : return 0dp[0] = 0dp[1] = 0for i in range(2,len(cost)+1):dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])return dp[len(cost)]