前言

这道题不算难， 写这个纯粹是因为我得强迫症， 必须要把自己说出来的例题写完。。。有没有评论给点鼓励或者建议呀！？

例题：爬楼梯的最小花费

题目描述：数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯

输入：cost = [10, 15, 20]
输出：15
解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。

题目链接： 746. 使用最小花费爬楼梯 - 力扣（LeetCode） (leetcode-cn.com)

分析

动态规划三要素

• 无后效性： 你爬到某一阶台阶， 此时花费为X， 你继续向后爬的时候，费用只是在X上进行累加， 但是与怎么得到X的毫无关系！
• 最优子结构：其实这个的分析就相当于最短路径一样， 用反证法去分析——如果你选择的台阶可得到最小花费， 那么走到中间一个台阶 i 的花费也应该是最小花费， 自己用反证法证明一下， 如果不会， 参看动态规划解析_索利亚噶通的博客-CSDN博客 
• 重叠子问题： 某阶台阶的计算结果可作为子问题去计算后面一阶和两阶台阶的结果

解题

• 定义状态dp[i]: 爬到第 i 阶台阶的最小花费
• 状态转移方程： dp[i] = min(dp[i-1], dp[i-2]) + cost[i]
• 初始化： dp[0] = 0, dp[1] = cost[0]

代码

class Solution:
    def minCostClimbingStairs(self, cost):
        length = len(cost)
        if length < 2:
            return 0

        dp = [0] * (length + 1)
        dp[1] = cost[0]

        for i in range(2, length + 1):
            dp[i] = min(dp[i-1], dp[i - 2]) + cost[i-1]

        return min(dp[length], dp[length-1])