[LeetCode 746. Min Cost Climbing Stairs(Easy)] JavaScript Dynamic Programming Solution

題目：

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.

理解：

計算出走到頂點的最少花費，可以選擇一次走一步或兩步，也可以選擇從第一階或最底部開始走。

想法：

也是聯想到 graph 的概念，從頂部開始往下找出到達某個點的最小值，因此直覺用 recursion 來解。

First Submission (Implemented by myself)

時間：半小時

虛擬碼：

declare minPath function with length as input
  base case: length <= 1, return 0
  declare path 1 = calculate the cost of climbing one step, call minPath with length - 1 as input
  declare path 2 = calculate the cost of climbing two step, call minPath with length - 2 as input
  find the minimun path and return it

實作：

結果：

Time Limit Exceeded

Time complexity: O(2^n)

Space complexity: O(n)

Second Submission (Dynamic Programming)

前一個解法重複計算很多次一樣的 minPath(n)，所以改用物件把計算過的值存在來，下次再遇到時值出從物件中取得就好，減少再次計算的時間。

實作：

結果：

Success

Time complexity: O(n), minPath gets called from 0 to n.

Space complexity: O(n) to keep the recursion stack and object.

Third Submission (Refer to Solution, Bottom-Up)

前一個解法是使用 recursion 從頂部往下算，參考解答後發現另外可用從底部往上算的解法。另外，前一個解法用物件存計算過的值，其實也可以用陣列來存，取用速度較物件快。

實作：

結果：

Success

Time complexity: O(n), because we iterate n-1 times, and each iteration takes O(1) time.

Space complexity: O(n) to keep the array.

Fourth Submission (Refer to Solution, Bottom-Up, Constant Space)

使用從底部開始的 iteration 解法，因為我們只需要一個到達頂部的最小值，不需要把過程都記在陣列裡，所以還有另一種更節省空間的寫法。

實作：

結果：

Success

Time complexity: O(n), because we iterate n-1 times, and each iteration takes O(1) time.

Space complexity: O(1) to keep two variables.