前言

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

涵蓋技術內容：Java后端、算法、分布式微服務、中間件、前端、運維、ROS等。

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

視頻平臺：b站-Coder長路

---

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

題目與分類

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

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

---

思路

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

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

復雜度分析：時間復雜度O(n)；空間復雜度O(n)

class Solution {//1000個空間//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];//初始下標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];}
}

---

資料獲取

大家點贊、收藏、關注、評論啦~

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

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

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