LeetCode：746. 使用最小花费爬楼梯【动态规划】

题目描述

思路

经典动态规划题，要求到楼顶的最低花费，首先要求到达楼顶前的两层花费，要求这两层的花费，则需要知道这两层的前两层的花费…
假设dp[i]表示第i层的最低花费，需要知道第i-1层和第i-2层的消费那层更少，再加上第i层的消费。于是dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]。

AC代码

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