跳转至

746. 使用最小花费爬楼梯

力扣链接(简单)：https://leetcode.cn/problems/min-cost-climbing-stairs

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

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

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

示例 1：

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

示例 2：

Text Only
 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

个人题解

动态规划五步曲：

  1. 确定 dp[i] 含义：到第 i 个台阶所花费的最少体力；
  2. 确定递推公式：dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])；
  3. dp 数组初始化：由题，到达下标为 0/1 的台阶不需要体力；
  4. 确定遍历顺序：dp[i] 由 dp[i - 1], dp[1 - 2] 推导，即从前向后遍历；
  5. 模拟推导 dp 数组，结果合理，开始 coding!
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    const int N = 1010;
    int minCostClimbingStairs(vector<int>& cost) {
        // 1. 确定 dp[i] 含义：到第 i 个台阶所花费的最少体力
        // 注意，dp 楼顶下标是 cost.size()
        int dp[N];
        // 由于每次支付费用后可以爬 1-2 个台阶，所有有两条路线到达 i ，选择费用小的一条路线
        // 2. 确定递推公式：dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
        // 3. dp 数组初始化。由题，到达下标为 0/1 的台阶不需要体力
        dp[0] = 0, dp[1] = 0;
        // 4. 确定遍历顺序：dp[i] 由 dp[i - 1], dp[1 - 2] 推导，即从前向后遍历
        // 5. 模拟推导 dp 数组，结果合理，开始 coding!

        for(int i = 2; i <= cost.size(); i++) {
            dp[i] = min(dp[i - 1] +cost[i - 1], dp[i - 2] + cost[i - 2]);
        }

        return dp[cost.size()];
    }
};