746 使用最小花费爬楼梯

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

题解

动态规划三部曲

1.定义dp数组和下标定义 dp表示到达第i个台阶的最小花费

2.定义递推公式 假设你现在在i个台阶上，那么怎么到第i个台阶花费最小呢，可以是从i-1个台阶上花费cost[i-1],也可以从i-2个台阶上花费cost[i-2]。那么我们需要取最小值。 dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])

3.递归的初始值和递归顺序 //因为可以直接站到下标为0 或者1的台阶上 dp[0]=0 dp[1]=0 dp[2]=min(cost[0], cost[1])

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

同时使用滚动数组来降低空间复杂度

var minCostClimbingStairs3 = function(cost) {
    var prev = 0
    var current = 0
    const n = cost.length;
    for(let i=2;i<=n;i++) {
        const newCurrent =  Math.min(current + cost[i-1], prev + cost[i-2])
        prev = current
        current = newCurrent
    }

    return current
}