746. Min Cost Climbing Stairs

skinner 發(fā)布于2019-07-30 17:08 / 2051人閱讀

746. Min Cost Climbing Stairs

On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).

Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.
Example:

Input: cost = [10, 15, 20]
Output: 15
Explanation: Cheapest is start on cost[1], pay that cost and go to the top.

Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].

Solution:

class Solution:
    def minCostClimbingStairs(self, cost):
        """
        :type cost: List[int]
        :rtype: int
        """
        start_0 = 0
        start_1 = 0
        for each in cost[::-1]:
            old_start_1 = start_1
            start_1 = start_0
            start_0 = min(start_0 + each, old_start_1 + each)
        return min(start_0, start_1)

云服務(wù)器 GPU云服務(wù)器 Climbing Stairs Cost min

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/42032.html

相關(guān)文章

leetcode 746 Min Cost Climbing Stairs

摘要：同時你可以選擇從第階開始或者第一階開始。我們的目標(biāo)是找出你爬到最頂層所付出的最小的開銷。最低開銷是，從第階開始，只花費(fèi)就可以到頂層。想法動態(tài)規(guī)劃問題。的長度應(yīng)該為數(shù)組長度加一，其中數(shù)組的最后一個元素的值就是本題的答案，最低開銷。題目詳情 On a staircase, the i-th step has some non-negative cost cost[i] assigned ...

fyber 2019-08-16 11:01 評論0 收藏0
前端 | 每天一個 LeetCode

摘要：在線網(wǎng)站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學(xué)習(xí)。這篇文章記錄我練習(xí)的 LeetCode 題目，語言 JavaScript。在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0
[Leetcode] Climbing Stairs 爬樓梯

摘要：遞歸法復(fù)雜度時間空間思路這題幾乎就是求解斐波那契數(shù)列。最簡單的方法就是遞歸。但重復(fù)計算時間復(fù)雜度高。代碼遞推法復(fù)雜度時間空間思路實際上我們求的時候只需要和的值，所以可以減少一些空間啊。 Climbing Stairs You are climbing a stair case. It takes n steps to reach to the top. Each time you c...

tinyq 2019-08-14 12:26 評論0 收藏0
[leetcode] Climbing Stairs

摘要：實質(zhì)就是把之前出現(xiàn)過的中間結(jié)果記錄，下次再出現(xiàn)相同情況的時候，通過可以只用的時間復(fù)雜度得到。表示到達(dá)第層樓梯的不同走法。那么題目中每次可以選擇走一步，或者兩步，。從迭代公式可以知道，有兩個，和。 70. Climbing Stairs You are climbing a staircase. It takes n steps to reach to the top.Each tim...

int64 2019-08-14 16:50 評論0 收藏0
[LintCode] Climbing Stairs II

Problem A child is running up a staircase with n steps, and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child can run up the stairs. Ex...

chengtao1633 2019-08-15 13:32 評論0 收藏0