每日一道算法題--leetcode 746--使用最小花費(fèi)爬樓梯--python

Euphoria 發(fā)布于2019-05-27 17:41 / 3170人閱讀

摘要：代碼思路最簡(jiǎn)單的一維動(dòng)態(tài)規(guī)劃問(wèn)題，自底向上。上代碼看效果，時(shí)間復(fù)雜度線(xiàn)性級(jí)別這里有一個(gè)動(dòng)態(tài)規(guī)劃系列題目整理，供大家參考

【題目描述】

??！題干里的示例1需要仔細(xì)看一下哦，要到達(dá)頂層，即20那一層，可以跳過(guò)20這一層達(dá)到更高一層，也因此我們給cost數(shù)組最后加一個(gè)元素0，模擬最頂層的上一層無(wú)須花費(fèi)力氣。

【代碼思路】 最簡(jiǎn)單的一維動(dòng)態(tài)規(guī)劃問(wèn)題，自底向上。

【上代碼】

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

看效果，時(shí)間復(fù)雜度線(xiàn)性級(jí)別：

這里有一個(gè)動(dòng)態(tài)規(guī)劃系列題目整理，供大家參考： blog.csdn.net/liukcqu/art…

云服務(wù)器 GPU云服務(wù)器爬樓梯最小角python算法 python走迷宮算法題最小生成樹(shù)python算法

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

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

相關(guān)文章

LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

摘要：微信公眾號(hào)記錄截圖記錄截圖目前關(guān)于這塊算法與數(shù)據(jù)結(jié)構(gòu)的安排前。已攻略返回目錄目前已攻略篇文章。會(huì)根據(jù)題解以及留言?xún)?nèi)容，進(jìn)行補(bǔ)充，并添加上提供題解的小伙伴的昵稱(chēng)和地址。本許可協(xié)議授權(quán)之外的使用權(quán)限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目錄不...

warmcheng 2019-08-26 10:09 評(píng)論0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

摘要：月下半旬攻略道題，目前已攻略題。目前簡(jiǎn)單難度攻略已經(jīng)到題，所以后面會(huì)調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時(shí)，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。一目錄不折騰的前端，和咸魚(yú)有什么區(qū)別...

tain335 2019-08-26 10:28 評(píng)論0 收藏0
LeetCode 之 JavaScript 解答第70題 —— 爬樓梯（Climbing Stair

摘要：小鹿題目假設(shè)你正在爬樓梯。需要階你才能到達(dá)樓頂。你有多少種不同的方法可以爬到樓頂呢注意給定是一個(gè)正整數(shù)。算法思路二種解決思路，第一利用遞歸第二利用動(dòng)態(tài)規(guī)劃。就是因?yàn)橛辛酥貜?fù)元素的計(jì)算，導(dǎo)致了時(shí)間復(fù)雜度成指數(shù)的增長(zhǎng)。 Time：2019/4/12Title:Clibing SrairsDifficulty: EasyAuthor:小鹿題目：Climbing Stairs You a...

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

摘要：在線(xiàn)網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。這篇文章記錄我練習(xí)的 LeetCode 題目，語(yǔ)言 JavaScript。在線(xiàn)網(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
第7期 Datawhale 組隊(duì)學(xué)習(xí)計(jì)劃

馬上就要開(kāi)始啦這次共組織15個(gè)組隊(duì)學(xué)習(xí) 涵蓋了AI領(lǐng)域從理論知識(shí)到動(dòng)手實(shí)踐的內(nèi)容按照下面給出的最完備學(xué)習(xí)路線(xiàn)分類(lèi) 難度系數(shù)分為低、中、高三檔可以按照需要參加 - 學(xué)習(xí)路線(xiàn) - showImg(https://segmentfault.com/img/remote/1460000019082128); showImg(https://segmentfault.com/img/remote/...

dinfer 2019-06-26 18:55 評(píng)論0 收藏0