題目連結:

https://leetcode.com/problems/min-cost-climbing-stairs/

參考解法:

https://www.youtube.com/watch?v=v3WqNLmmBdk

法ㄧ(Recursive version):

var dp: [Int] = []
func minCostClimbingStairs(_ cost: [Int]) -> Int {
    dp = Array(repeating: -1, count: cost.count + 1)
    return helper(cost, cost.count)
}

func helper(_ cost: [Int], _ steps: Int) -> Int {
    if steps <= 1 {
        return 0
    } else if dp[steps] != -1 {
        return dp[steps]
    } else {
        dp[steps] = min(helper(cost, steps - 1) + cost[steps - 1], helper(cost, steps - 2) + cost[steps - 2])
        return dp[steps]
    }
}

法二(Iterative version):

func minCostClimbingStairs(_ cost: [Int]) -> Int {
    if cost.count == 0 || cost.count == 1 {
        return 0
    } else {
        var dp = Array(repeating: -1, count: cost.count + 1)
        dp[0] = 0
        dp[1] = 0
        for i in 2 ... cost.count {
            dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
        }
        return dp[cost.count]
    }
}