每日一道算法题--leetcode 746--使用最小花费爬楼梯--python

栏目: Python · 发布时间: 4年前

内容简介：！！题干里的示例1需要仔细看一下哦，要到达顶层，即20那一层，可以跳过20这一层达到更高一层，也因此我们给cost数组最后加一个元素0，模拟最顶层的上一层无须花费力气。【代码思路】最简单的一维动态规划问题，自底向上。看效果，时间复杂度线性级别：

【题目描述】

每日一道算法题--leetcode 746--使用最小花费爬楼梯--python

！！题干里的示例1需要仔细看一下哦，要到达顶层，即20那一层，可以跳过20这一层达到更高一层，也因此我们给cost数组最后加一个元素0，模拟最顶层的上一层无须花费力气。

【代码思路】最简单的一维动态规划问题，自底向上。

【上代码】

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        len1=len(cost)
        cost.append(0)
        dp=[]
        dp.append(cost[0])
        dp.append(cost[1])
        for i in range(2,len1+1):
            dp.append(min(dp[i-1],dp[i-2])+cost[i])
        return min(dp[len1-1],dp[len1])
复制代码

看效果，时间复杂度线性级别：

这里有一个动态规划系列题目整理，供大家参考： blog.csdn.net/liukcqu/art…

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。

码农书籍

编写可读代码的艺术

Boswell, D.、Foucher, T. / 尹哲、郑秀雯 / 机械工业出版社 / 2012-7-10 / 59.00元

细节决定成败，思路清晰、言简意赅的代码让程序员一目了然；而格式凌乱、拖沓冗长的代码让程序员一头雾水。除了可以正确运行以外，优秀的代码必须具备良好的可读性，编写的代码要使其他人能在最短的时间内理解才行。本书旨在强调代码对人的友好性和可读性。本书关注编码的细节，总结了很多提高代码可读性的小技巧，看似都微不足道，但是对于整个软件系统的开发而言，它们与宏观的架构决策、设计思想、指导原则同样重要。编......一起来看看《编写可读代码的艺术》这本书的介绍吧!

码农工具

CSS 压缩/解压工具

在线压缩/解压 CSS 代码

HSV CMYK 转换工具

HSV CMYK互换工具