代码随想录刷题第三十八天| 理论基础 ● 509. 斐波那契数 ● 70. 爬楼梯 ● 746. 使用最小花费爬楼梯

发布时间：2024年01月06日

代码随想录刷题第三十八天

动态规划基础理论

在这里插入图片描述

斐波那契数 (LC 509)

题目思路：

在这里插入图片描述

代码实现：

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

爬楼梯 (LC 70)

题目思路：

在这里插入图片描述

代码实现：

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

使用最小花费爬楼梯 (LC 746)

题目思路：

在这里插入图片描述

代码实现：

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        if len(cost)<=1:
            return 0
            
        dp = [0 for _ in range(len(cost)+1)]
        
        for 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)]
文章来源:https://blog.csdn.net/shaozi25/article/details/135420735
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
最新文章