代码随想录算法训练营Day38 | 动态规划理论基础、509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯 | Python | 个人记录向

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

注：Day37休息。

动态规划理论基础

代码随想录：动态规划理论基础

动规五部曲：

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

509. 斐波那契数

代码随想录：509. 斐波那契数
Leetcode：509. 斐波那契数

做题

class Solution:def fib(self, n: int) -> int:if n == 0 or n == 1:return nf = [0] * (n+1)f[0] = 0f[1] = 1i = 2while i <= n:f[i] = f[i-1] + f[i-2]i += 1return f[n]  

时间复杂度: O(n)
空间复杂度: O(n)

看文章

可以只维护两个数值。
时间复杂度: O(n)
空间复杂度: O(1)

70. 爬楼梯

代码随想录：70. 爬楼梯
Leetcode：70. 爬楼梯

做题

往上一格和两格加上当前的方法数，初始值为1。但感觉有点懵懵的。

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

时间复杂度：O(n)
空间复杂度：O(n)

看文章

其实类似斐波那契数。

空间复杂度为O(n)版本

class Solution:def climbStairs(self, n: int) -> int:if n <= 1:return ndp = [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]

空间复杂度为O(3)版本

# 空间复杂度为O(3)版本
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):total = dp[1] + dp[2]dp[1] = dp[2]dp[2] = totalreturn dp[2]

把dp[1]和dp[2]改为常变量，就变成O(1)了。

746. 使用最小花费爬楼梯

代码随想录：746. 使用最小花费爬楼梯
Leetcode：746. 使用最小花费爬楼梯

做题

直接在cost数组上做计算即可。

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

时间复杂度：O(n)
空间复杂度：O(1)，使用原始数组不算空间复杂度

看文章

思路差不多。

以往忽略的知识点小结

• 动规如果只需要保存前几个数，可以用几个常变量保存，降低空间复杂度
• 可以举例推导dp数组，然后打印日志来debug

个人体会

完成时间：1h20min。
心得：动规刚开始，需要理清思路，今天都AC了。

​

这篇关于代码随想录算法训练营Day38 | 动态规划理论基础、509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯 | Python | 个人记录向的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---