LeetCode-746.爬楼梯最小花费

发表于 分类于

题目描述

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

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

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

示例

1
2
3
4
5
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。
1
2
3
4
5
6
7
8
9
10
输入：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 。

提示

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

题解

使用动态规划思想：

要到达第i级台阶的上面，可以是从i-1级台阶跨1步上去f(i-1) + cost[i - 1] ，也可以是从i-2级台阶上跨2步上去f(i-2)+cost[i-2]，所以 f[i]=min(f(i−1)+cost[i−1],f(i−2)+cost[i−2])。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func minCostClimbingStairs(_ cost: [Int]) -> Int {
  if cost.count == 0 {
    return 0
  }
  if cost.count == 1 {
    return 0
  }
  var preOfPre = 0
  var pre = 0
  for i in 2 ... cost.count {
    let cur = min(preOfPre + cost[i-2], pre + cost[i-1])
    preOfPre = pre
    pre = cur
  }

  return pre
}