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

前言

在这个问题中，我们有一个数组 $cost[]$，其中 $cost[i]$ 表示从第 $i$ 个台阶爬到下一个台阶的费用。你可以从第 $0$ 个台阶或第 $1$ 个台阶开始，然后每次可以选择爬 $1$ 个台阶或 $2$ 个台阶。题目要求的是：你到达楼顶时花费的最小费用是多少?

你需要计算的是，在爬到楼顶时，花费的最小费用。楼顶位于 $cost$ 数组的末尾之后的一个位置，即爬完最后一个台阶后，你就到达了楼顶。

题目描述

基本思路

1. 问题定义:

在这个问题中，我们有一个数组 $cost[]$，其中 $cost[i]$ 表示从第 $i$ 个台阶爬到下一个台阶的费用。你可以从第 $0$ 个台阶或第 $1$ 个台阶开始，然后每次可以选择爬 $1$ 个台阶或 $2$ 个台阶。题目要求的是：你到达楼顶时花费的最小费用是多少?

你需要计算的是，在爬到楼顶时，花费的最小费用。楼顶位于 $cost$ 数组的末尾之后的一个位置，即爬完最后一个台阶后，你就到达了楼顶。

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

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

• 假设 $dp[i]$ 是爬到第 $i$ 个台阶的最小花费。
• 你可以从 $i-1$ 或者 $i-2$ 台阶爬到第 $i$ 个台阶。相应地，爬到第 $i$ 台阶的最小花费是前面两阶的最小花费，加上 $\mathrm{cost}[i]$ ：

$$dp[i]=\min (dp[i-1],dp[i-2])+\mathrm{cost}[i]$$

到达楼顶的情况是你从第 $n-1$ 或 $n-2$ 台阶爬上去，而楼顶没有对应的花费。

3. 解决方法:

1. 初始条件: 你可以从第 $\theta$ 或第 1 个台阶开始。因此 $dp[\theta ]=\mathrm{cost}[\theta ],dp[1]=\mathrm{cost}[1]$ 。
2. 递推公式：对于第 $i$ 个台阶， $dp[i]=\min (dp[i-1],dp[i-2])+\mathrm{cost}[i]$ 。
3. 目标: 计算出 $dp[n-1]$ 或 $dp[n-2]$ 的最小值，因为到达楼顶时你可能是从这两个台阶之一爬上去的。

4. 进一步优化:

我们注意到在每一步递推时， $dp[i]$ 只依赖于 $dp[i-1]$ 和 $dp[i-2]$ ，因此可以用两个变量代替整个 dp[] 数组，减少空间复杂度。

• 时间复杂度： $O(n)$ ，因为我们只需要遍历一次数组。
• 空间复杂度： $O(1)$ ，只需要常量空间保存前两阶的最小费用。

5. 小总结:

• 本质是一个动态规划问题，通过递推公式 $dp[i]=\min (dp[i-1],dp[i-2])+\mathrm{cost}[i]$ 来逐步计算。
• 我们可以通过优化将空间复杂度从 $O(n)$ 降低到 $O(1)$ 。
• 目标是计算出到达楼顶的最小花费，最后从 $n-1$ 或 $n-2$ 台阶上去。

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

代码实现

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: 如果 $cost[]$ 长度为 0 或 1 ，直接返回最小花费。
2. 动态规划：用 prev2 和 prev1 存储爬到前两个台阶的最小花費，并依次更新。
3. 最终结果：返回最后两个台阶中较小的花费。

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: 如果 $cost[]$ 长度为 0 或 1 ，直接返回最小花费。
2. 动态规划：用两个变量 prev2 和 prev1 来存储前两个台阶的最小花费，通过循环不断更新。
3. 最终结果：返回最后两个台阶的最小花费。

---

总结:

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

原文地址：https://blog.csdn.net/AlbertDS/article/details/142464848

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！