746. 使用最小花费爬楼梯 🟩

题目

LeetCode 简单

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

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

示例 2：
输入：cost = [1, 100, 1, 1, 1, 100 , 1 , 1 , 100 , 1]
输出：6
解释：
你将从下标为 0 的台阶开始。
1）支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
2）支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
3）支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
4）支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
5）支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
6）支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。

题解

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

DP

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

function minCostClimbingStairs(cost) {
  const len = cost.length
  const dp = [cost[0], cost[1]]
  for (let i = 2; i <= len; i++) {
    console.log('♻️ i', i)
    console.log(
      'dp[i - 2]',
      dp[i - 2],
      'dp[i - 1]',
      dp[i - 1],
      'cost[i]',
      cost[i],
    )

    dp[i] = Math.min(dp[i - 2], dp[i - 1]) + (cost[i] || 0)

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

const cost = [10, 15, 20]
console.log('🌰', minCostClimbingStairs(cost))

执行结果

♻️ i 2
dp[i - 2] 10 dp[i - 1] 15 cost[i] 20
dp [10,15,30]
♻️ i 3
dp[i - 2] 15 dp[i - 1] 30 cost[i] undefined
dp [10,15,30,15]
🌰 15

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

DP

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

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

本页目录