746.使用最小花费爬楼梯

使用最小花费爬楼梯

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

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

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

示例 1：

输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。支付 15，向上爬两个台阶，到达楼梯顶部。总花费为 15。

示例 2：

输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。依次经过 0、2、4、6、8 号台阶，总花费为 6。

提示：

• 2 <= cost.length <= 1000
• 0 <= cost[i] <= 999

解析

动态规划，dp[i] 表示到达第 i 个台阶的最小花费。由于可以从第 i-1 或第 i-2 个台阶到达，所以 dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])。

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

空间优化后只需要 O(1) 的额外空间，时间复杂度 O(n)。