【LeetCode】动态规划—使用最小花费爬楼梯（附完整Python/C++代码）

动态规划—#746. 使用最小花费爬楼梯

• 前言
• 题目描述
• 基本思路
  • 1. 问题定义:
  • 2. 理解问题和递推关系:
  • 3. 解决方法:
  • 4. 进一步优化:
  • 5. 小总结:
• 代码实现
• • Python3代码实现
  • Python 代码解释
  • C++代码实现
  • C++ 代码解释
• 总结:

前言

在这个问题中，我们有一个数组

，其中

表示从第

个台阶爬到下一个台阶的费用。你可以从第

个台阶或第

个台阶开始，然后每次可以选择爬

个台阶或

个台阶。题目要求的是：你到达楼顶时花费的最小费用是多少?

你需要计算的是，在爬到楼顶时，花费的最小费用。楼顶位于

数组的末尾之后的一个位置，即爬完最后一个台阶后，你就到达了楼顶。

题目描述

在这里插入图片描述

基本思路

1. 问题定义:

在这个问题中，我们有一个数组

，其中

表示从第

个台阶爬到下一个台阶的费用。你可以从第

个台阶或第

个台阶开始，然后每次可以选择爬

个台阶或

个台阶。题目要求的是：你到达楼顶时花费的最小费用是多少?

你需要计算的是，在爬到楼顶时，花费的最小费用。楼顶位于

数组的末尾之后的一个位置，即爬完最后一个台阶后，你就到达了楼顶。

2. 理解问题和递推关系:

到达楼顶的最小费用可以通过递推计算:

• 假设

是爬到第

个台阶的最小花费。

• 你可以从

或者

台阶爬到第

个台阶。相应地，爬到第

台阶的最小花费是前面两阶的最小花费，加上

：

到达楼顶的情况是你从第

或

台阶爬上去，而楼顶没有对应的花费。

3. 解决方法:

1. 初始条件: 你可以从第

或第 1 个台阶开始。因此

。

1. 递推公式：对于第

个台阶，

。

1. 目标: 计算出

或

的最小值，因为到达楼顶时你可能是从这两个台阶之一爬上去的。

4. 进一步优化:

我们注意到在每一步递推时，

只依赖于

和

，因此可以用两个变量代替整个 dp[] 数组，减少空间复杂度。

• 时间复杂度：

，因为我们只需要遍历一次数组。

• 空间复杂度：

，只需要常量空间保存前两阶的最小费用。

5. 小总结:

• 本质是一个动态规划问题，通过递推公式

来逐步计算。

• 我们可以通过优化将空间复杂度从

降低到

。

• 目标是计算出到达楼顶的最小花费，最后从

或

台阶上去。

以上就是使用最小花费爬楼梯问题的基本思路。

代码实现

Python3代码实现

class Solution:
    def minCostClimbingStairs(self, cost: list[int]) -> int:
        # 如果台阶数少于 2 直接返回最低的花费
        if len(cost) == 0:
            return 0
        elif len(cost) == 1:
            return cost[0]
        
        # 初始化前两个台阶的最小花费
        prev2 = cost[0]
        prev1 = cost[1]
        
        # 从第3个台阶开始（即索引2），逐步计算每个台阶的最小花费
        for i in range(2, len(cost)):
            current = min(prev1, prev2) + cost[i]
            prev2 = prev1  # 更新前一个台阶的花费
            prev1 = current  # 更新当前台阶的花费
        
        # 到达楼顶的最小花费可以从倒数第一或倒数第二个台阶上去
        return min(prev1, prev2)

Python 代码解释

1. Base Case: 如果

长度为 0 或 1 ，直接返回最小花费。

1. 动态规划：用 prev2 和 prev1 存储爬到前两个台阶的最小花費，并依次更新。
2. 最终结果：返回最后两个台阶中较小的花费。

C++代码实现

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        // 如果台阶数少于2，直接返回最低的花费
        if (cost.size() == 0) return 0;
        if (cost.size() == 1) return cost[0];
        
        // 初始化前两个台阶的最小花费
        int prev2 = cost[0];
        int prev1 = cost[1];
        
        // 从第3个台阶开始（即索引2），逐步计算每个台阶的最小花费
        for (int i = 2; i < cost.size(); ++i) {
            int current = min(prev1, prev2) + cost[i];
            prev2 = prev1;  // 更新前一个台阶的花费
            prev1 = current;  // 更新当前台阶的花费
        }
        
        // 到达楼顶的最小花费可以从倒数第一或倒数第二个台阶上去
        return min(prev1, prev2);
    }
};

C++ 代码解释

1. Base Case: 如果

长度为 0 或 1 ，直接返回最小花费。

1. 动态规划：用两个变量 prev2 和 prev1 来存储前两个台阶的最小花费，通过循环不断更新。
2. 最终结果：返回最后两个台阶的最小花费。

总结:

• 该问题的核心是动态规划，通过递推公式计算每个台阶的最小花费。
• 为了优化空间复杂度，我们只使用两个变量来存储前两阶的最小花费。
• 通过 Python 和 C++ 的实现，可以有效计算出爬到楼顶的最小费用。