LeetCode Js-746. Min Cost Climbing Stairs

    AllenLi
    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

    Related Posts