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

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

内容简介：！！题干里的示例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])
复制代码

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