Easy

题目描述

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

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

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

示例 1：

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

示例 2：

输入：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. 楼梯顶部可以看作是下标 n（数组长度）的位置
  3. 状态转移方程：dp[i] = cost[i] + min(dp[i+1], dp[i+2])
    • 从第 i 个台阶出发，支付 cost[i] 后，可以到达 i+1 或 i+2 位置
  4. 边界条件：dp[n] = dp[n+1] = 0（已经到达顶部，无需花费）

解法优化：

  • 方法一：使用 dp 数组从后往前计算
  • 方法二：空间优化，只用两个变量存储后两个状态（推荐）

由于每次只需要用到后面两个状态，我们可以用两个变量来优化空间复杂度。从后往前遍历，不断更新这两个变量即可。

最终答案是 min(dp[0], dp[1])，因为我们可以从第 0 或第 1 个台阶开始。

代码实现

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        int next1 = 0, next2 = 0;  // dp[i+1], dp[i+2]
        
        for (int i = n - 1; i >= 0; i--) {
            int current = cost[i] + min(next1, next2);
            next2 = next1;
            next1 = current;
        }
        
        return min(next1, next2);
    }
};

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        next1, next2 = 0, 0  # dp[i+1], dp[i+2]
        
        for i in range(n - 1, -1, -1):
            current = cost[i] + min(next1, next2)
            next2 = next1
            next1 = current
        
        return min(next1, next2)

public class Solution {
    public int MinCostClimbingStairs(int[] cost) {
        int n = cost.Length;
        int next1 = 0, next2 = 0;  // dp[i+1], dp[i+2]
        
        for (int i = n - 1; i >= 0; i--) {
            int current = cost[i] + Math.Min(next1, next2);
            next2 = next1;
            next1 = current;
        }
        
        return Math.Min(next1, next2);
    }
}

var minCostClimbingStairs = function(cost) {
    const n = cost.length;
    let next1 = 0, next2 = 0;  // dp[i+1], dp[i+2]
    
    for (let i = n - 1; i >= 0; i--) {
        const current = cost[i] + Math.min(next1, next2);
        next2 = next1;
        next1 = current;
    }
    
    return Math.min(next1, next2);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型数组DP解法空间优化解法（推荐）
时间复杂度O(n)O(n)
空间复杂度O(n)O(1)

相关题目