算法题day41（补5.27日卡：动态规划01）

一、动态规划基础知识：在动态规划中每一个状态一定是由上一个状态推导出来的。

动态规划五部曲：

1.确定dp数组 以及下标的含义

2.确定递推公式

3.dp数组如何初始化

4.确定遍历顺序

5.举例推导dp数组

debug方式：打印

二、刷题：

1.leetcode题目 509. 斐波那契数 - 力扣（LeetCode）（easy)

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

2.leetcode题目 70. 爬楼梯 - 力扣（LeetCode）（easy）

解决：

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

3.leetcode题目 746. 使用最小花费爬楼梯 - 力扣（LeetCode）

解决：

class Solution:def minCostClimbingStairs(self, cost: List[int]) -> int:dp = [0] * (len(cost) + 1)dp[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)]