描述

746.使用最小花費(fèi)爬樓梯
數(shù)組的每個(gè)下標(biāo)作為一個(gè)階梯，第 i 個(gè)階梯對(duì)應(yīng)著一個(gè)非負(fù)數(shù)的體力花費(fèi)值 cost[i]（下標(biāo)從 0 開(kāi)始）。

每當(dāng)你爬上一個(gè)階梯你都要花費(fèi)對(duì)應(yīng)的體力值，一旦支付了相應(yīng)的體力值，你就可以選擇向上爬一個(gè)階梯或者爬兩個(gè)階梯。

請(qǐng)你找出達(dá)到樓層頂部的最低花費(fèi)。在開(kāi)始時(shí)，你可以選擇從下標(biāo)為 0 或 1 的元素作為初始階梯。

示例 1：

輸入：cost = [10, 15, 20]
輸出：15
解釋：最低花費(fèi)是從 cost[1] 開(kāi)始，然后走兩步即可到階梯頂，一共花費(fèi) 15 。
示例 2：

輸入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
輸出：6
解釋：最低花費(fèi)方式是從 cost[0] 開(kāi)始，逐個(gè)經(jīng)過(guò)那些 1 ，跳過(guò) cost[3] ，一共花費(fèi) 6 。

提示：
cost 的長(zhǎng)度范圍是 [2, 1000]。
cost[i] 將會(huì)是一個(gè)整型數(shù)據(jù)，范圍為 [0, 999] 。

思路：動(dòng)態(tài)規(guī)劃

//1.確定dp[i]數(shù)組與下標(biāo)的含義：達(dá)到第i個(gè)臺(tái)階所花費(fèi)的最少體力//2.確定遞推公式:有兩個(gè)途徑得到dp[i];首先選取上一步dp[i-1]跟dp[i-2]中最小的,// 然后加上當(dāng)前臺(tái)階的花費(fèi)dp[i] = min(dp[i-1], dp[i-2]) + cost[i];//3.dp數(shù)組初始化:dp[0]是第0個(gè)臺(tái)階,dp[1]是第1個(gè)臺(tái)階//4.確定遍歷順序//5.舉例推導(dǎo)dp數(shù)組

時(shí)間復(fù)雜度:O(n)
空間復(fù)雜度:O(n)

class Solution { public:int minCostClimbingStairs(vector<int>& cost) {//1.確定dp[i]數(shù)組與下標(biāo)的含義：達(dá)到第i個(gè)臺(tái)階所花費(fèi)的最少體力//2.確定遞推公式//3.dp數(shù)組初始化//4.確定遍歷順序//5.舉例推導(dǎo)dp數(shù)組vector<int> dp(cost.size()); //初始化dp數(shù)組大小dp[0] = cost[0]; //確定初始條件,到達(dá)第0個(gè)臺(tái)階最少花費(fèi)在第0個(gè)costdp[1] = cost[1]; //到達(dá)第1個(gè)臺(tái)階最少花費(fèi)在第1個(gè)的costfor(int i=2;i<cost.size();i++){dp[i] = min(dp[i-1], dp[i-2]) + cost[i];}//由于最后一步可以不用花費(fèi)所以取return min(dp[cost.size()-1],dp[cost.size()-2]);} };

優(yōu)化動(dòng)態(tài)規(guī)劃

時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(1)

class Solution { public:int minCostClimbingStairs(vector<int>& cost) {//1.確定dp[i]數(shù)組與下標(biāo)的含義：達(dá)到第i個(gè)臺(tái)階所花費(fèi)的最少體力//2.確定遞推公式:有兩個(gè)途徑得到dp[i];首先選取上一步dp[i-1]跟dp[i-2]中最小的,// 然后加上當(dāng)前臺(tái)階的花費(fèi)dp[i] = min(dp[i-1], dp[i-2]) + cost[i];//3.dp數(shù)組初始化:dp[0]是第0個(gè)臺(tái)階,dp[1]是第1個(gè)臺(tái)階//4.確定遍歷順序//5.舉例推導(dǎo)dp數(shù)組// vector<int> dp(cost.size()); //初始化dp數(shù)組大小// dp[0] = cost[0]; //確定初始條件,到達(dá)第0個(gè)臺(tái)階最少花費(fèi)在第0個(gè)cost// dp[1] = cost[1]; //到達(dá)第1個(gè)臺(tái)階最少花費(fèi)在第1個(gè)的cost// for(int i=2;i<cost.size();i++){// dp[i] = min(dp[i-1], dp[i-2]) + cost[i];// }// //由于最后一步可以不用花費(fèi)所以取// return min(dp[cost.size()-1],dp[cost.size()-2]);vector<int> dp(2);dp[0] = cost[0];dp[1] = cost[1];for(int i=2;i<cost.size();i++){int sum = min(dp[0], dp[1]) + cost[i];dp[0] = dp[1];dp[1] = sum;}return min(dp[0], dp[1]);} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode-动态规划基础题-746. 使用最小花费爬楼梯的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。