【题目描述】
!!题干里的示例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…