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

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

动规开始

动归：有很多重叠子问题--状态能顺次推导，后一个动作受到前面动作的影响

（比如前一个动作占了背包的空间 后一个动作受剩下的空间的限制

贪心：每次都是取最小 不受挤压空间干扰）

DP的debug：推导DP数组--print出来看是否符合预期

09. 斐波那契数
只需要维护2个数 就一直往前移动 我感觉这个我写的很好看

class Solution:def fib(self, n: int) -> int:if n<=1: return ndp0,dp1=0,1for i in range(2,n+1):dp0,dp1=dp1,dp0+dp1return dp1

 70. 爬楼梯

和上一题其实一样 但0也是一种走法

class Solution:def climbStairs(self, n: int) -> int:dp0,dp1=1,1for i in range(2,n+1):dp0,dp1=dp1,dp0+dp1return dp1

 不跳步版本：dp[n]=dp[n-1]+dp[n-2]

class Solution:def climbStairs(self, n: int) -> int:if n<=1: return ndp1,dp2=1,2for i in range(3,n+1):dp1,dp2=dp2,dp1+dp2return dp2

 746. 使用最小花费爬楼梯

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

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

---