最小花费爬楼梯（动态规划）-Toy模板网

这篇具有很好参考价值的文章主要介绍了最小花费爬楼梯（动态规划）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目：

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。

输入格式：
n 个整数，代表从第 n - 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

思路和算法（动态规划）：

        假设数组 cost 的长度为 n，则 n 个阶梯分别对应下标 0 到 n - 1，楼层顶部对应下标 n，问题等价于计算达到下标 n 的最小花费。可以通过动态规划求解。
        创建长度为 n + 1 的数组 minCost，其中 minCost[i] 表示达到下标 i 的最小花费。由于可以选择下标 0 或 1 作为初始阶梯，因此有 minCost[0] = minCost[1] = 0。
        当 2≤i≤n 时，可以从下标 i - 1 使用 cost[i−1] 的花费达到下标 i，或者从下标 i - 2 使用 cost[i−2] 的花费达到下标 i。为了使总花费最小，minCost[i] 应取上述两项的最小值，因此状态转移方程如下：

minCost[i] = min(minCost[i−1] + cost[i−1], minCost[i−2] + cost[i−2])

依次计算 minCost 中的每一项的值，最终得到的 minCost[n] 即为达到楼层顶部的最小花费。

#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;

int minCostClimbingStairs(vector<int>& cost) {
    //int n = cost.size();
    //int* minCost = new int[n];
    //minCost[0] = minCost[1] = 0;
    //for (int i = 2; i <= n; i++)
    //{
    //    minCost[i] = min(minCost[i - 1] + cost[i - 1], minCost[i - 2] + cost[i - 2]);
    //}
    //return minCost[n];

    int n = cost.size();
    vector<int> minCost(n + 1);              //定义一个到达第 i 层台阶所需的最小花费容器
    minCost[0] = minCost[1] = 0;             //可从第0层和第1层开始，这两层不需要抵达所需花费
    for (int i = 2; i <= n; i++) {
        minCost[i] = min(minCost[i - 1] + cost[i - 1], minCost[i - 2] + cost[i - 2]);
    }
    return minCost[n];                       //返回到达最后一层的最小花费
}

int main() {
    int num;
    vector<int> cost;
    // cost 的长度始终比 i 大，除非输入回车否则输入不会停止（实现输入 n 个整数）
    for (int i = 0; i < cost.size() + 1; i++) {
        cin >> num;
        cost.push_back(num);                  // push.back() 函数，将数据放入 cost
        if (cin.get() == '\n')  break;        //当输入回车的时候退出循环
    }
    cout << minCostClimbingStairs(cost);
    return 0;
}

复杂度分析：
时间复杂度：O(n)，其中 n 是数组 cost 的长度。需要依次计算每个 minCost 值，每个值的计算需要常数时间，因此总时间复杂度是 O(n)。
空间复杂度：O(1)。使用滚动数组的思想，只需要使用有限的额外空间。

作者：LeetCode - Solution
链接：https ://leetcode.cn/problems/min-cost-climbing-stairs/solution/shi-yong-zui-xiao-hua-fei-pa-lou-ti-by-l-ncf8/
来源：力扣（LeetCode）
文章来源地址https://www.toymoban.com/news/detail-723426.html

到了这里，关于最小花费爬楼梯（动态规划）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！