leetcode 每日一题：746. 使用最小花费爬楼梯

一起刷题吧

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

示例 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

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]