题目
给你一个整数数组
cost，其中cost[i]是从楼梯第i个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
限制条件
- 2 <= cost.length <= 1000
- 0 <= cost[i] <= 999
Show me the code
class Solution {var cacheMap = [Int: Int]()func minCostClimbingStairs(_ cost: [Int]) -> Int {return minCostClimbingStairs(cost, cost.count)}func minCostClimbingStairs(_ cost: [Int], _ prefixCount: Int) -> Int {if let cache = cacheMap[prefixCount] {return cache}if prefixCount == 2 {return min(cost[0], cost[1])}if prefixCount == 3 {return min(cost[0] + cost[2], cost[1])}let ret = min(minCostClimbingStairs(cost, prefixCount - 1) + cost[prefixCount - 1], minCostClimbingStairs(cost, prefixCount - 2) + cost[prefixCount - 2])cacheMap[prefixCount] = retreturn ret}
}
执行用时&内存分布
