zhangdi

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

题目 ​

LeetCode 简单

INFO

给你一个整数数组 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)

ts
function minCostClimbingStairs(cost: number[]): number {
  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))

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

DP O(n) O(1)

ts
function minCostClimbingStairs2(cost: number[]): number {
  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 cost2 = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
console.log('🌰', minCostClimbingStairs2(cost2))