大家好，我是晴天學長，很重要的思想動規思想，需要的小伙伴可以關注支持一下哦！后續會繼續更新的。💪💪💪
1）使用最小花費爬樓梯
給你一個整數數組 cost ，其中 cost[i] 是從樓梯第 i 個臺階向上爬需要支付的費用。一旦你支付此費用，即可選擇向上爬一個或者兩個臺階。
你可以選擇從下標為 0 或下標為 1 的臺階開始爬樓梯。
請你計算并返回達到樓梯頂部的最低花費。
示例 1：
輸入：cost = [10,15,20]
輸出：15
解釋：你將從下標為 1 的臺階開始。
支付 15 ，向上爬兩個臺階，到達樓梯頂部。
總花費為 15 。
示例 2：
輸入：cost = [1,100,1,1,1,100,1,1,100,1]
輸出：6
解釋：你將從下標為 0 的臺階開始。
- 支付 1 ，向上爬兩個臺階，到達下標為 2 的臺階。
- 支付 1 ，向上爬兩個臺階，到達下標為 4 的臺階。
- 支付 1 ，向上爬兩個臺階，到達下標為 6 的臺階。
- 支付 1 ，向上爬一個臺階，到達下標為 7 的臺階。
- 支付 1 ，向上爬兩個臺階，到達下標為 9 的臺階。
- 支付 1 ，向上爬一個臺階，到達樓梯頂部。
總花費為 6 。
提示：
2 <= cost.length <= 1000
0 <= cost[i] <= 999
2) .算法思路
- 有點像變了的樣子的打家劫舍，可以打劫附近的房子了。
3) .算法步驟
定義一個整型數組 memo 和 cost，用于存儲記憶化搜索的結果和每個樓梯的代價。
創建 minCostClimbingStairs 方法來啟動算法。在該方法中，初始化 memo 數組和 cost 數組，并將 memo 數組的所有元素初始化為 -1。
調用 dfs 方法，將起始索引設為 cost.length - 1（最后一個樓梯），并返回從最后一個樓梯開始上樓梯的最小代價。
在 dfs 方法中，首先檢查是否已經搜索過當前索引 i 的結果。如果在 memo 數組中存在已計算的值，則直接返回該值作為結果，避免重復計算。
如果當前索引 i 小于 0，表示已經超出樓梯范圍，返回 0。
否則，根據動態規劃的思想，當前樓梯 i 的最小代價等于從前一個樓梯 i-1 或者前兩個樓梯 i-2 上來的最小代價加上當前樓梯的代價。使用遞歸調用 dfs 方法，分別計算從 i-1 樓梯和 i-2 樓梯上來的最小代價，并將它們與當前樓梯的代價相加并取最小值。
將計算得到的結果存儲在 memo 數組中，以備后續使用。
返回當前索引 i 的結果作為最終答案，即從最后一個樓梯出發的最小代價。
4）.代碼示例
方法1：記憶化搜索。class Solution {int[] memo;int[] cost;public int minCostClimbingStairs(int[] cost) {memo = new int[1000];this.cost = cost;Arrays.fill(memo, -1);return Math.min(dfs(cost.length - 1), dfs(cost.length - 2));}//變相的打家劫舍, 到樓梯發現已經爬上來了，不能選擇不爬private int dfs(int i) {if (i < 0) return 0;if (memo[i] != -1) return memo[i];int result = Math.min(dfs(i - 1) + cost[i], dfs(i - 2) + cost[i]);memo[i] = result;return result;}}
方法2：動態規劃dp
//感興趣的小伙伴可以用一個數組來打表，優化空間復雜度。class Solution {public int minCostClimbingStairs(int[] cost) {int[] dp = new int[cost.length];dp[0] = cost[0];dp[1] = cost[1];for (int i = 2; i < dp.length; i++) {dp[i] = Math.min(dp[i - 1] + cost[i], dp[i - 2] + cost[i]);}return Math.min(dp[cost.length - 1], dp[cost.length - 2]);}}
5）.總結
- 狀態轉移思想。
試題鏈接：
)
