Re: [閒聊] 每日LeetCode已回收
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
推
10/13 12:27,
2年前
, 1F
10/13 12:27, 1F
→
10/13 12:27,
2年前
, 2F
10/13 12:27, 2F
→
10/13 12:28,
2年前
, 3F
10/13 12:28, 3F
推
10/13 12:30,
2年前
, 4F
10/13 12:30, 4F
→
10/13 12:32,
2年前
, 5F
10/13 12:32, 5F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 445 之 719 篇)：