zhangdizhangdi

746.使用最小花费爬楼梯

题目

LeetCode 简单

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上 爬一个或者两个 台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。

示例：
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。

  • 支付 15 ，向上爬两个台阶，到达楼梯顶部。

总花费为 15 。

输入：cost = [1, 100, 1, 1, 1, 100 , 1 , 1 , 100 , 1]
输出：6
解释：你将从下标为 0 的台阶开始。

  • 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
  • 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
  • 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
  • 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
  • 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
  • 支付 1 ，向上爬一个台阶，到达楼梯顶部。

总花费为 6 。

题解

方法：空间复杂度 O(n)

DP O(n) O(n)

js
function minCostClimbingStairs(cost) {
  const len = cost.length
  const dp = [cost[0], cost[1]]
  for (let i = 2; i <= len; i++) {
    dp[i] = Math.min(dp[i - 2], dp[i - 1]) + (cost[i] || 0)

    console.log(dp)
  }
  return dp[len]
}

const cost = [10, 15, 20]
console.log('🌰', minCostClimbingStairs(cost))
执行结果
[ 10, 15, 30 ]
[ 10, 15, 30, 15 ]
🌰 15

方法：空间复杂度 O(1)

DP O(n) O(1)

js
function minCostClimbingStairs(cost) {
  const len = cost.length
  let res = 0
  let p2 = cost[0] //前面第二个
  let p1 = cost[1] //前面一个
  for (let i = 2; i <= len; i++) {
    res = Math.min(p2, p1) + (cost[i] || 0)
    p2 = p1
    p1 = res

    console.log('i', i, 'p2', p2, 'p1', p1, 'res', res)
  }
  return res
}

const cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
console.log('🌰', minCostClimbingStairs(cost))
执行结果
i 2 p2 100 p1 2 res 2
i 3 p2 2 p1 3 res 3
i 4 p2 3 p1 3 res 3
i 5 p2 3 p1 103 res 103
i 6 p2 103 p1 4 res 4
i 7 p2 4 p1 5 res 5
i 8 p2 5 p1 104 res 104
i 9 p2 104 p1 6 res 6
i 10 p2 6 p1 6 res 6
🌰 6