代码随想录算法训练营day41 | 509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯

本文主要是介绍代码随想录算法训练营day41 | 509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

509. 斐波那契数

• 确定dp数组以及下标的含义：dp[i]的定义为：第i个数的斐波那契数值是dp[i]
• 确定递推公式：dp[i] = dp[i - 1] + dp[i - 2]
• dp数组如何初始化：dp[0] = 0 dp[1] = 1
• 确定遍历顺序：从前向后
• 举例推导dp数组

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

70. 爬楼梯

• 确定dp数组以及下标的含义：dp[i]为爬上i阶楼梯有多少方法
• 确定递推公式：dp[i] = dp[i-1] + dp[i-2]
• dp数组如何初始化：dp[1] = 1 dp[2] = 2
• 确定遍历顺序：从前向后遍历
• 举例推导dp数组

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

746. 使用最小花费爬楼梯

• 确定dp数组以及下标的含义：dp[i]代表爬上第i个台阶的最低花费
• 确定递推公式：dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
• dp数组如何初始化：dp[0] = 0 dp[1] = 0
• 确定遍历顺序：从前向后遍历
• 举例推导dp数组

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

这篇关于代码随想录算法训练营day41 | 509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---