Leetcode746-使用最小花费爬楼梯-Python实现

• 题目要求：

• 思路：

  • 动态规划
  • 上当前的楼梯花费的体力最小值为，前一个楼梯和前面两个楼梯中较小的那一个加上当前楼梯需要花费的体力值
  • 维护一个数组 dp 用来保存上所有台阶需要花费的体力值，初始化前两个元素，第一个元素为 0，第二个元素为上第一个台阶需要花费的体力值
  • 遍历数组，从下标位置为 1 开始遍历，因为下标位置为 0 的元素，也就是上第一个台阶所要花费的体力值已经保存在数组中了
  • 遍历结束后，数组 dp 的末尾两个元素中较小的就是花费最小的，因为从 dp[-1] 的那个元素可以一步走到阶梯顶，dp[-2] 的元素也可以一步走到阶梯顶。
• 核心代码：

dp = [0, cost[0]]
for i in range(1, len(cost)):
    dp.append(min(dp[i] + cost[i], dp[i - 1] + cost[i]))
return min(dp[-1], dp[-2])

• 完整代码：

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

• 因为只需要前一个台阶和前两个台阶，所以可以不用数组，维护两个值即可：

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        if not cost:
            return 0
        pre, cur = 0, cost[0]
        dp = [0, cost[0]]
        for i in range(1, len(cost)):
            pre, cur = cur, min(pre + cost[i], cur + cost[i])
        return min(pre, cur)