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

三、相似題目

這個題目有個相似題目：70. 爬樓梯：https://leetcode-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]

同樣也可以對空間做優化，這裡就不實現了