LeetCode Js-746. Min Cost Climbing Stairs

    LeetCode Js-Optimization

    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.

    你給予一個整數陣列價格,而 cost[i] 為每個 i 步驟的成本。
    支付費用之後,你可以選擇爬一階或兩階梯。
    你可以從第 0 階或第 1 階開始。
    回傳到達樓層頂部的最小的成本。
    

    Example 1:

    Input: cost = [10,15,20]
    Output: 15
    Explanation: You will start at index 1.
    - Pay 15 and climb two steps to reach the top.
    The total cost is 15.
    

    Example 2:

    Input: cost = [1,100,1,1,1,100,1,1,100,1]
    Output: 6
    Explanation: You will start at index 0.
    - Pay 1 and climb two steps to reach index 2.
    - Pay 1 and climb two steps to reach index 4.
    - Pay 1 and climb two steps to reach index 6.
    - Pay 1 and climb one step to reach index 7.
    - Pay 1 and climb two steps to reach index 9.
    - Pay 1 and climb one step to reach the top.
    The total cost is 6.
    

    Solution:
    1. 宣告 step1 和 step2 分別為 10 和 15。
    2. 執行 For 迴圈,i 從 2 步驟開始。
    3. 步驟倆倆比對取最小為 temp。
    4. 將更新後的 temp 再與下一個步驟成本比較取最小值。

    cost: [10, 15, 20] 
    
    +---+---------+--------+--------+
    | i | cost[i] | path.1 | path.2 |
    +---+---------+--------+--------+
    | 0 | 10      | Start  |   -    |
    | 1 | 15      | 0 -> 1 | Start  |
    | 2 | 20      |   -    |   -    |
    | 3 | NULL    | 1 -> 3 | 1 -> 3 |
    +---+---------+--------+--------+
    cost ---------|10 + 15 |   15   |
                  +--------+--------+
    

    Code:

    var minCostClimbingStairs = function(cost) {
        let [step1, step2] = cost
      
        for (let i = 2; i < cost.length; i++) {
          let temp = Math.min(step1, step2) + cost[i]
          step1 = step2
          step2 = temp
        }
    
        return Math.min(step1, step2)
    }
    

    FlowChart:
    Example 1

    Input: cost = [10,15,20]
    
    step.1
    temp = min(10, 15) + cost(2) => 10 + 20 = 30
    step1 = step2 //15
    step2 = temp //30
    
    return min(step1, step2) = min(15, 30) //15
    

    Example 2

    Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
             i  =  0,   1, 2, 3, 4,   5, 6, 7,   8, 9
    
    step.1 
    temp = min(1, 100) + cost(2) => 1 + 1 = 2
    step1 = step2 //100
    step2 = temp //2
    
    step.2
    temp = min(100, 2) + cost(3) => 2 + 1 = 3
    step1 = step2 //2
    step2 = temp //3
    
    step.3
    temp = min(2, 3) + cost(4) => 2 + 1 = 3
    step1 = step2 //3
    step2 = temp //3
    
    step.4
    temp = min(3, 3) + cost(5) => 3 + 100 = 103
    step1 = step2 //3
    step2 = temp //103
    
    step.5
    temp = min(3, 103) + cost(6) => 3 + 1 = 4
    step1 = step2 //103
    step2 = temp //4
    
    step.6
    temp = min(103, 4) + cost(7) => 4 + 1 = 5
    step1 = step2 //4
    step2 = temp //5
    
    step.7
    temp = min(4, 5) + cost(8) => 4 + 100 = 104
    step1 = step2 //5
    step2 = temp //104
    
    step.8
    temp = min(5, 104) + cost(9) => 5 + 1 = 6
    step1 = step2 //104
    step2 = temp //6
    
    return min(step1, step2) = min(104, 6) //6