746.使用最小花费爬楼梯

题目来源:力扣

题目描述:

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

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

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

示例:

 

我的代码:(错误代码)

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        int m = 0;
        if (n == 1) {
            m += cost[0];
        }
        for (int i = n; i >= 2;) {
            if (cost[i - 1] < cost[i - 2]) {
                m += cost[i - 1];
                i = i - 1;
            } else {
                m += cost[i - 2];
                i = i - 2;
            }
        }
        return m;
    }
};

我使用了倒序和贪心的想法,同时也通过了大部分例子,我的错误在于使用倒序,这会导致前几层开始的最少花费无法选中,因为每次只能爬1或者2层,从而错过前几层的选择

错误出现在这里,我的代码对于这种情况无解

题解

方法来源于官方

思路讲解:
我们就使用0,2,2,1这个数组来举例

这里画图方便理解,我们看cost数组,里面存放了0,2,2,1,他有四个元素,我们最后需要爬到的层数是第四层,所以我们创建n+1的数组dp,dp里的元素代表我们爬到下标层已经花费的费用,因为我们可以从0和1层出发,所以dp的0和1都为0,我们看下标为2时,我们可以从第0层和第一层开始爬,假设我们从第0层开始爬,我们需要花费cost[0](爬这层需要支付的费用)+ dp[0](爬到这层已经花费的最少费用),二者之和为0,我们再看从第一层开始爬,计算出结果为2,对比0和2,可知我们爬到第2层最少花费为0,也就是从第0层开始爬,向上爬2层

我们再看i=3时,也就是我们需要爬到第三层时,计算得出最少花费为2,再看i=4,也就是到终点时,我们可以从第3层或者第2层开始爬,假设我们从第三层开始爬,需要花费cost[3](爬这层需要支付的费用)+ dp[3](爬到这层已经花费的最少费用),结果为3,假设我们从第二层开始爬,需要花费cost[2](爬这层需要支付的费用)+ dp[2](爬到这层已经花费的最少费用),计算得出结果为2,所以我们爬到第四层需要花费的最少费用即为2

代码:(正确答案)

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

相关推荐

  1. 746.使用花费楼梯

    2024-07-11 18:22:03       60 阅读
  2. 746. 使用花费楼梯

    2024-07-11 18:22:03       67 阅读
  3. 746. 使用花费楼梯

    2024-07-11 18:22:03       54 阅读
  4. LeetCode 746. 使用花费楼梯

    2024-07-11 18:22:03       72 阅读
  5. 动态规划 Leetcode 746 使用花费楼梯

    2024-07-11 18:22:03       41 阅读
  6. LeetCode 746. 使用花费楼梯

    2024-07-11 18:22:03       39 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-11 18:22:03       98 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-11 18:22:03       106 阅读
  3. 在Django里面运行非项目文件

    2024-07-11 18:22:03       87 阅读
  4. Python语言-面向对象

    2024-07-11 18:22:03       97 阅读

热门阅读

  1. 表单代码示例

    2024-07-11 18:22:03       28 阅读
  2. Unity中短路法在背包系统的应用

    2024-07-11 18:22:03       22 阅读
  3. 3133. 数组最后一个元素的最小值

    2024-07-11 18:22:03       27 阅读
  4. windows脚本获取 svn版本号

    2024-07-11 18:22:03       24 阅读
  5. 力扣题解(摆动序列)

    2024-07-11 18:22:03       25 阅读
  6. 搭建discuz论坛(lvs+nginx+http+mysql+nfs)8台服务器

    2024-07-11 18:22:03       23 阅读
  7. 【AI大模型】如何在企业环境中部署GPT-3/GPT-4模型

    2024-07-11 18:22:03       28 阅读
  8. 图论学习 c++Ford-Fulkerson 方法

    2024-07-11 18:22:03       26 阅读
  9. 主线程结束子线程不再执行

    2024-07-11 18:22:03       28 阅读