前言

博主介紹：?目前全網(wǎng)粉絲2W+，csdn博客專家、Java領(lǐng)域優(yōu)質(zhì)創(chuàng)作者，博客之星、阿里云平臺(tái)優(yōu)質(zhì)作者、專注于Java后端技術(shù)領(lǐng)域。

涵蓋技術(shù)內(nèi)容：Java后端、算法、分布式微服務(wù)、中間件、前端、運(yùn)維、ROS等。

博主所有博客文件目錄索引：博客目錄索引(持續(xù)更新)

視頻平臺(tái)：b站-Coder長(zhǎng)路

---

LeetCode、746. 使用最小花費(fèi)爬樓梯【簡(jiǎn)單，動(dòng)態(tài)規(guī)劃 線性DP】

題目與分類

題目鏈接：LeetCode、746. 使用最小花費(fèi)爬樓梯【簡(jiǎn)單，動(dòng)態(tài)規(guī)劃 線性DP】

題目類型：動(dòng)態(tài)規(guī)劃/線性DP（一維DP）

---

思路

思路描述：我們可以使用一個(gè)dp數(shù)組，第i個(gè)位置保存當(dāng)前最耗費(fèi)最小的費(fèi)用，接著初始化第0、1個(gè)臺(tái)階值，對(duì)于之后的臺(tái)階位置我們都可以使用一個(gè)遞推方程：d

p(i) = Math.min(dp(i - 1), dp(i - 2)) + cost[i]，最終返回頂部位置也就是dp[n]即可就是最小花費(fèi)答案。

復(fù)雜度分析：時(shí)間復(fù)雜度O(n)；空間復(fù)雜度O(n)

class Solution {//1000個(gè)空間//dp(i) = Math.min(dp(i - 1), dp(i - 2)) + cost[i]public int minCostClimbingStairs(int[] cost) {int n = cost.length;//定義dp數(shù)組int[] dp = new int[n + 1];//初始下標(biāo)0、1位置dp[0] = cost[0];dp[1] = cost[1];//遞推方程for (int i = 2; i <= n; i ++) {dp[i] = Math.min(dp[i - 1], dp[i - 2]) + (i < n ? cost[i] : 0);}return dp[n];}
}

---

資料獲取

大家點(diǎn)贊、收藏、關(guān)注、評(píng)論啦~

精彩專欄推薦訂閱：在下方專欄👇🏻

• 長(zhǎng)路-文章目錄匯總（算法、后端Java、前端、運(yùn)維技術(shù)導(dǎo)航）：博主所有博客導(dǎo)航索引匯總
• 開源項(xiàng)目Studio-Vue—校園工作室管理系統(tǒng)(含前后臺(tái)，SpringBoot+Vue)：博主個(gè)人獨(dú)立項(xiàng)目，包含詳細(xì)部署上線視頻，已開源
• 學(xué)習(xí)與生活-專欄：可以了解博主的學(xué)習(xí)歷程
• 算法專欄：算法收錄

更多博客與資料可查看👇🏻獲取聯(lián)系方式👇🏻，🍅文末獲取開發(fā)資源及更多資源博客獲取🍅