动态规划

动态规划中每一个状态一定是由上一个状态推导出来的
动态规划五步曲：

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

做动规的题目，写代码之前一定要把状态转移在dp数组的上具体情况在纸上模拟一遍

509. 斐波那契数

题目链接： 509. 斐波那契数 - 力扣（LeetCode）

代码

class Solution:def fib(self, n: int) -> int:if n == 0:return 0dp = [0]*(n+1)dp[1] = 1for i in range(2,n+1):dp[i] = dp[i-1]+dp[i-2]return dp[n]

70. 爬楼梯

题目链接： 70. 爬楼梯 - 力扣（LeetCode）

思路

1. dp[i]的含义是爬到i层台阶的方法数

代码

class Solution:def climbStairs(self, n: int) -> int:if n == 1:return 1dp = [0]*(n+1)dp[1] = 1dp[2] = 2for i in range(3,n+1):dp[i] = dp[i-1]+dp[i-2]return dp[n]

746. 使用最小花费爬楼梯

题目链接： 746. 使用最小花费爬楼梯 - 力扣（LeetCode）

思路

1. dp[i]的含义是爬到i层台阶的最低花费

代码

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

优化时间复杂度

class Solution:def minCostClimbingStairs(self, cost: List[int]) -> int:cost.append(0)dp0 = cost[0]dp1 = cost[1]for i in range(2,len(cost)):dp = min(dp0,dp1)+cost[i]dp0 = dp1dp1 = dpreturn dp1