编辑代码

/** 
    1、确定dp数组(dp table)以及下标的含义
    2、确定递推公式
    3、dp数组如何初始化
    4、确定遍历顺序
    5、举例推导dp数组


    数组的每个下标作为一个阶梯,第 i 个阶梯对应着一个非负数的体力花费值 cost[i](下标从 0 开始)。
    每当你爬上一个阶梯你都要花费对应的体力值,一旦支付了相应的体力值,你就可以选择向上爬一个阶梯或者爬两个阶梯。
    请你找出达到楼层顶部的最低花费。在开始时,你可以选择从下标为 0 或 1 的元素作为初始阶梯。
    示例 1:
    输入:cost = [10, 15, 20] 输出:15 
    解释:最低花费是从 cost[1] 开始,然后走两步即可到阶梯顶,一共花费 15 。  示例 2:
    输入:cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] 输出:6 
    解释:最低花费方式是从 cost[0] 开始,逐个经过那些 1 ,跳过 cost[3] ,一共花费 6 。
    提示:
    cost 的长度范围是 [2, 1000]。
    cost[i] 将会是一个整型数据,范围为 [0, 999] 。

    1、dp[i]代表到达第层阶梯需要花费的体力
    2、dp[i] = min(dp[i-1], dp[i-2]) + cost[i]
    3、cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
        dp  = [1,100,  2, 3, 3, 103, 4, 5, 104, 6] 
*/

function main(cost) {
    let len = cost.length
    let dp = [1,100]
    if(len <= 2) return cost[len-1]
    for(let i= 3; i<=len; i++) {
        dp[i-1] = Math.min(dp[i-2], dp[i-3]) + cost[i-1]
    }
    return dp[len-1]
}
console.log(main([1, 100, 1, 1, 1, 100, 1, 1, 100, 1]))
// 时间复杂度:O(n)
// 空间复杂度:O(n)

function main2(cost) {
    let len = cost.length
    let dp = [1,100]
    if(len <= 2) return cost[len-1]
    for(let i= 3; i<=len; i++) {
        // dp[i-1] = Math.min(dp[i-2], dp[i-3]) + cost[i-1]
        let now = Math.min(dp[0], dp[1]) + cost[i-1]
        dp[0] = dp[1]
        dp[1] = now
    }
    return dp[1]
}
console.log(main2([1, 100, 1, 1, 1, 100, 1, 1, 100, 1]))
// 时间复杂度:O(n)
// 空间复杂度:O(1)