746. Min Cost Climbing Stairs

- 2 minutes read - 511 words

Leetcode 746. Min Cost Climbing Stairs

題目

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

想法

這個階梯問題最一般的方法應該會是用 DP 來做。

因為到第 x 階所要花的總 cost 就會是到第 x - 1 階（最後再跨 1 步到 x）或到第 x - 2 階（最後再跨 2 步到 x）兩者之間的較小總 cost 再加上第 x 階自己的 cost。

那用一個 DP 陣列，初始放第一階及第二階的 cost，跑上去答案就會出來了。

再仔細想想，其實連 DP 陣列都不用，因為每次只會需要前兩階的總 cost。

可以用像滾輪的方式，類似像 DP 概念一樣慢慢滾上去，就有答案了。

實作

Javascript

var minCostClimbingStairs = function (cost) {
    // 注意：第 x 階的 cost 是 cost[x - 1]，x > 0
    // top 是第 n + 1 階

    // 差一步「之前」的總 cost 跟差兩步「之前」的總 cost，起始 0 其實是第零階的 cost
    let one = 0,
        two = 0;
    
    // 滾上去，記得要滾到 cost.length
    for (let i = 2; i <= cost.length; i++) {
        // 每次往上一層，差一步「之前」的總 cost 會變成差兩步「之前」的總 cost，而新的差一步「之前」的總 cost 則會是原本差一步「之前」的總 cost + 差一步的 cost 與原本差兩步「之前」的總 cost + 差兩步的 cost，兩者較小值
        [one, two] = [one + cost[i - 1] < two + cost[i - 2] ? one + cost[i - 1] : two + cost[i - 2], one];
    }

    // 最後輸出的其實是到 n + 1 階差一步「之前」的總 cost
    return one;
};