746. Min Cost Climbing Stairs

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

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)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/42032.html

相關(guān)文章

leetcode 746 Min Cost Climbing Stairs

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

fyber 2019-08-16 11:01 評(píng)論0 收藏0
前端 | 每天一個(gè) LeetCode

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

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

摘要：遞歸法復(fù)雜度時(shí)間空間思路這題幾乎就是求解斐波那契數(shù)列。最簡(jiǎn)單的方法就是遞歸。但重復(fù)計(jì)算時(shí)間復(fù)雜度高。代碼遞推法復(fù)雜度時(shí)間空間思路實(shí)際上我們求的時(shí)候只需要和的值，所以可以減少一些空間啊。 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 評(píng)論0 收藏0
[leetcode] Climbing Stairs

摘要：實(shí)質(zhì)就是把之前出現(xiàn)過(guò)的中間結(jié)果記錄，下次再出現(xiàn)相同情況的時(shí)候，通過(guò)可以只用的時(shí)間復(fù)雜度得到。表示到達(dá)第層樓梯的不同走法。那么題目中每次可以選擇走一步，或者兩步，。從迭代公式可以知道，有兩個(gè)，和。 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 評(píng)論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 評(píng)論0 收藏0