Programming
Leetcode-746. Min Cost Climbing Stairs
<解題> 遞迴版本
- 計算爬到第 n 階的最小花費，即 cost[n] 加上爬到前一階和前兩階中花費較小的那個的最小花費。這是因為我們可以選擇爬到前一階或前兩階，然後再加上爬到當前階所需的花費：
- 遞迴關係：cost[i] += Math.min(cost[i-1], cost[i-2]);
- 最後return Math.min(cost[cost.length-1], cost[cost.length-2]);
class Solution {
public int minCostClimbingStairs(int[] cost) {
for(int i = 2 ; i < cost.length ; i++){
cost[i] += Math.min(cost[i-1], cost[i-2]);
}
return Math.min(cost[cost.length-1], cost[cost.length-2]);
}
}
Time: O(n) Space: O(1)