LeetCode演算法題-Min Cost Climbing Stairs(Java實現)
這是悅樂書的第307 次更新,第327 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第176題(順位題號是746)。在樓梯上,第i步有一些非負成本成本[i]分配(0索引)。一旦支付了費用,您可以爬一到兩步。您需要找到到達樓層頂部的最低成本,您可以從索引為0的步驟開始,也可以從索引為1的步驟開始。例如:
輸入:cost= [10,15,20]
輸出:15
說明:最便宜的是從成本[1]開始,支付該成本並返回頂部。
輸入:cost= [1,100,1,1,1,100,1,1,100,1]
輸出:6
說明:最便宜的是從成本[0]開始,並且僅在1上跳,跳過成本[3]。
注意:
-
成本陣列的長度在[2,1000]範圍內。
-
每個成本[i]將是[0,999]範圍內的整數。
本次解題使用的開發工具是eclipse,jdk使用的版本是1.8,環境是win7 64位系統,使用Java語言編寫和測試。
02 第一種解法
題目的意思是在成本陣列中找出成本總和最小的組合,遍歷完陣列,遍歷時可以跨一個單位或兩個單位,和之前的爬樓梯的題目有點類似。我們可以推敲一下,如果要爬到第i級樓梯,有兩種選擇,一是從第i-1級爬上來,二是從第i-2級階梯爬上來,然後取其中兩者的成本值,哪個花費小,就選哪個。對此我們新建一個數組dp,來儲存前面每次選擇後要花費的成本之和。
因此,我們可以得出一個關係:dp[i] = Math.min(之前爬兩次的花費+當前此次是爬兩步的花費, 之前爬一次的花費+當前此次是爬一步的花費);依次計算取其中的較小值存入dp中即可,最後返回dp的最後一位元素。
public int minCostClimbingStairs(int[] cost) { int[] dp = new int[cost.length+1]; for (int i=2; i<cost.length+1; i++) { dp[i] = Math.min(dp[i-2]+cost[i-2], dp[i-1]+cost[i-1]); } return dp[dp.length-1]; }
03 第二種解法
我們還可以對上面的解法進行優化,不使用陣列單獨存每一次的計算結果,因為新的計算只是依賴前兩次的結果,所以我們使用了兩個臨時變數來儲存前兩次的計算值,思路和上面第一種解法還是一樣的。
public int minCostClimbingStairs(int[] cost) { int prev = 0, prev2 = 0, current = 0; for(int i = 2; i<cost.length+1; i++){ current = Math.min(cost[i-2]+prev2, cost[i-1]+prev); prev2 = prev; prev = current; } return current; }
04 小結
演算法專題目前已日更超過五個月,演算法題文章176+篇,公眾號對話方塊回覆【資料結構與演算法】、【演算法】、【資料結構】中的任一關鍵詞,獲取系列文章合集。
以上就是全部內容,如果大家有什麼好的解法思路、建議或者其他問題,可以下方留言交流,點贊、留言、轉發就是對我最大的回報和支援!