一起刷题吧

一、题目分析

输入：由数值组成的数组
输出：到达楼层顶部的最低花费
难度：简单
标签：贪心，动态规划

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

示例 2:
输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出: 6
解释: 最低花费方式是从cost[0]开始，逐个经过那些1，跳过cost[3]，一共花费6。

二、参考代码

这个题是动态规划里比较简单的题目，动态方程也比较好想：

F[i] 表示走到第 i 层需要的最小的步数，只是走到
F[i] = min(F[i-1] + cost[i-1], F[i-2] + cost[i-2])
最终结果是 F[len(cost)] 即走过第 len(cost)-1 层

参考代码如下：

from typing import List


class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        if not cost:
            return 0
        # F[i] 表示走到第 i 层需要的最小的步数，只是走到
        # F[i] = min(F[i-1] + cost[i-1], F[i-2] + cost[i-2])
        # 最终结果是 F[len(cost)] 即走过第 len(cost)-1 层

        F = [0] * (len(cost) + 1)

        for i in range(2, len(cost)+1):
            F[i] = min(F[i-1]+cost[i-1], F[i-2] + cost[i-2])
        return F[-1]

对空间做优化，只需要前两次的状态，不需要使用一个数组，优化代码如下：

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        if not cost:
            return 0
        # F[i] 表示走到第 i 层需要的最小的步数，只是走到
        # F[i] = min(F[i-1] + cost[i-1], F[i-2] + cost[i-2])
        # 最终结果是 F[len(cost)] 即走过第 len(cost)-1 层

        # 上一个，上上一个
        lp, fp = 0, 0
        for i in range(2, len(cost)+1):
            fp, lp = lp, min(lp+cost[i-1], fp + cost[i-2])
        return lp

三、相似题目

这个题目有个相似题目：70. 爬楼梯：eetcode-cn.com/problems/climbing-stairs/

这个题目的动态规划方程是类似的，这里直接给出实现代码：

class Solution:
    def climbStairs(self, n: int) -> int:
        if not n:
            return 0

        if n < 2:
            return 1

        # F[i] 表示到第 i 阶台阶需要多少步子
        # F[i] = F[i-1] + F[i-2]

        F = [0] * (n + 1)
        F[1] = 1
        F[2] = 2

        for i in range(3, n+1):
            F[i] = F[i-1] + F[i-2]
        return F[-1]

同样也可以对空间做优化，这里就不实现了