第273题(2020-08-06)：使用最小花费爬楼梯？（字节）

[qappleh]

No description provided.

[qappleh]

解法：动态规划

本题注意理解题意：

第 i 级台阶是第 i-1 级台阶的阶梯顶部。
踏上第 i 级台阶花费 cost[i] ，直接迈一大步跨过而不踏上去则不用花费。
楼梯顶部在数组之外，如果数组长度为 len，那么楼顶就在下标为 len

第一步：定义子问题

踏上第 i 级台阶的体力消耗为到达前两个阶梯的最小体力消耗加上本层体力消耗：

最后迈 1 步踏上第 i 级台阶：dp[i-1] + cost[i]
最后迈 1 步踏上第 i 级台阶：dp[i-2] + cost[i]

第二步：实现需要反复执行解决的子子问题部分

所以踏上第 i 级台阶的最小花费为：

dp[i] = min(dp[i-2], dp[i-1]) + cost[i]

第三步：识别并求解出边界条件

// 第 0 级 cost[0] 种方案 
dp[0] = cost[0]
// 第 1 级，有两种情况
// 1：分别踏上第0级与第1级台阶，花费cost[0] + cost[1]
// 2：直接从地面开始迈两步直接踏上第1级台阶，花费cost[1]
dp[1] = min(cost[0] + cost[1], cost[1]) = cost[1]

最后一步：把尾码翻译成代码，处理一些边界情况

let minCostClimbingStairs = function(cost) {
    cost.push(0)
    let dp = [], n = cost.length
    dp[0] = cost[0]
    dp[1] = cost[1]
    for(let i = 2; i < n; i++){
        dp[i] = Math.min(dp[i-2] , dp[i-1]) + cost[i]
    }
    return dp[n-1]
}

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(n)

优化：

let minCostClimbingStairs = function(cost) {
    let n = cost.length,
        n1 = cost[0],
        n2 = cost[1] 
    for(let i = 2;i < n;i++){
        let tmp = n2
        n2 = Math.min(n1,n2)+cost[i]
        n1 = tmp
    }
    return Math.min(n1,n2)
};

• 时间复杂度：O(n)
• 空间复杂度：O(1)

leetcode