【LeetCode】NO.746 使用最小花費怕樓梯(C++ & Python) [動态規劃]

動态規劃第二彈！！！

題目：使用最小花費爬樓梯

給你一個整數數組 cost ，其中 cost[i] 是從樓梯第 i 個台階向上爬需要支付的費用。一旦你支付此費用，即可選擇向上爬一個或者兩個台階。

你可以選擇從下标為 0 或下标為 1 的台階開始爬樓梯。

請你計算并傳回達到樓梯頂部的最低花費。

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/min-cost-climbing-stairs

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

思路

1. 到達最後一個樓梯之後還要在前進一步才能到達樓頂

2. 到達樓頂可以認為是前面走過的路花費最小的加上目前狀态下标的花費之後一步踏上樓頂

   當把每一個位置的最小花費求出來之後，選擇最後兩個中最小的那個，因為這個兩個都能到達樓頂，花費最小的那個才是答案；

代碼

C++ 版本

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> dp(cost.size());


        dp[0] = cost[0];
        dp[1] = cost[1];
        for(int i = 2; i<cost.size(); i++)
        {
            dp[i] = min(dp[i-1],dp[i-2])+cost[i];
        }
        for(int i=0; i<cost.size();i++)
        {
            cout<<dp[i]<<" ";
        }
        return min(dp[cost.size()-2],dp[cost.size()-1]);
    }
};

           

Python

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

           

本文來自部落格園，作者：jucw，轉載請注明原文連結：https://www.cnblogs.com/Jucw/p/15753787.html