推 wwndbk: 大師 10/13 12:27
→ wwndbk: 挖幹 java遞迴這麼簡單喔 10/13 12:27
→ Rushia: 這沒遞迴阿 迭代而已 10/13 12:28
推 wwndbk: 喔喔 看錯 10/13 12:30
→ wwndbk: 早上看題目以為這題會用到遞迴 10/13 12:32
https://leetcode.com/problems/min-cost-climbing-stairs/description
746. Min Cost Climbing Stairs
給你一個陣列 cost[] 表示每一層的成本，你需要爬樓梯到樓頂，你每次可以從當前
位置花費 cost[i] 走1步或2步，你從 0 或 1 出發，求出走到 cost.length 最小要
多少 cost。
思路：
1.動態規劃，位置 i 當前的成本只能是兩種情況：
* 往前一階的最小成本 + cost[i - 1]
* 往前兩階的最小成本 + cost[i - 2]
在這兩種情況取較小值就是當前的最小成本以此類推。
2.因為只需要用到 i - 2 之前的狀態，所以用額外兩個變數記錄就好。
Java Code：
--------------------------------------
class Solution {
public int minCostClimbingStairs(int[] cost) {
int minCost = 0;
int first = 0;
int second = 0;
for (int i = 2; i <= cost.length; i++) {
minCost = Math.min(cost[i - 1] + second, cost[i - 2] + first);
first = second;
second = minCost;
}
return minCost;
}
}
--------------------------------------
--
https://i.imgur.com/SzMl4X2.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1697171178.A.CB6.html