首页 > 其他分享 >刷刷刷 Day 38 | 746. 使用最小花费爬楼梯

刷刷刷 Day 38 | 746. 使用最小花费爬楼梯

时间:2023-02-26 22:55:55浏览次数:63  
标签:38 台阶 746 花费 上爬 cost 下标 Day dp

746. 使用最小花费爬楼梯

LeetCode题目要求

给你一个整数数组 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 。
解题思路

动规五部曲

  1. 确定数组, dp[i],第 i 阶需要花费 dp[i]
  2. 递推公式
    从 dp[i-1] 到达 dp[i] 花费 dp[i-1] + cost[i-1]
    从 dp[i-2] 到达 dp[i] 花费 dp[i-2] + cost[i-2]
    而使用哪个花费,就取最小值
  3. 初始数组
    由于可以从 0 或 1 开始,那么 dp[0]=0; dp[1]=0;
  4. 遍历顺序
    从前往后
  5. 举例推导
    索引: 0 1 2 3 4 5 6 7 8 9 楼顶
    cost: [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
    dp : 0 0 1 1 2 3 3 4 4 5 6
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int len = cost.length;
        int[] dp = new int[len+1];

        // 初始化数组,0 阶和 1 阶都 无花费
        dp[0] = 0;
        dp[1] = 0;

        // 从第二个索引开始遍历
        for (int i = 2; i <= len; i++) {
            // dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。
            int e1 = dp[i-1] + cost[i-1];
            // dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]
            int e2 = dp[i-2] + cost[i-2]; 
            // 取花费的最小值
            dp[i] = Math.min(e1, e2);
        }

        return dp[len];
    }
}
重难点

动规5步

附:学习资料链接

标签:38,台阶,746,花费,上爬,cost,下标,Day,dp
From: https://www.cnblogs.com/blacksonny/p/17158114.html

相关文章

  • 【题解】CTT 2020 Day 1
    目录A.术树数B.树数术C.述树术A.术树数注意到路径+环的组合仍然可行,因为我们可以在无影响的情况下加入环(显然一条边也算二元环)。而对于每条边,如果其在某些环内,只要......
  • 【题解】CTT 2020 Day 3
    目录A.计数鸡B.PerotationC.树特卡克林A.计数鸡考虑\(\sum\limits_{i}\sum\limits_{j>i}[p_i\geqp_j]+[(p_i+h_i)\geqq_j]\),前部分是逆序对,而偶数让人想到行列式......
  • 【题解】CTT 2019 Day 2
    目录A.循环序列B.MatrixC.杀蚂蚁简单版A.循环序列即求\(\sum\limits_{i=0}^{c}{k\choosem+in}\),即\(\frac{1}{n}\sum\limits_{j=0}^{n-1}\sum\limits_{i=0}^{k-m}......
  • 【题解】CTT 2019 Day 1
    目录A.递增树列B.异世界的文章分割者C.时间旅行A.递增树列令\(f_{u,i}\)表示\(u\)的子树,已经用掉\(i\)个点,剩下的点排列满足要求的方案数。考虑方案的计算,用......
  • 【题解】CTT 2018 Day 2
    目录A.宝石游戏B.面国建设C.WechatA.宝石游戏无修改时考虑长链剖分(加整体异或标记)。有修改时分块,不考虑关键点层长链剖分,最后算答案的时候处理关键点层的答案即可。......
  • Java学习day2
    Java学习day2  JavaDocjavadoc命令用来生成自己的API文档@author作者名@version版本号@since指明需要最早使用的jdk版本@param参数名@return返......
  • Java学习Day1
    Java学习-----day1 Java的三大版本:JavaSE:标准版(桌面程序,控制台开发...)JavaME:嵌入式开发(手机,小家电...)JavaEE:企业集开发(web端,服务器开发...)......
  • 刷刷刷 Day 38 | 70. 爬楼梯
    70.爬楼梯LeetCode题目要求假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢?示例输入:n=2输出:2解......
  • Day02
    常用的DOS命令#盘符切换c:(英文:)#查看当前目录下所有文件dir#切换目录cd(changedirectory)#返回上一级cd..#屏幕清理cls#退出终端exit#查看电脑的ipipcon......
  • 代码随想录 day0 博客怎么写
    前言2.25日开始记录自己的博客生涯以及代码随想录训练营的每日内容一、题目链接怎么找?怎么设置连接?力扣题目链接1:力扣二、正文怎么写?二分查找算法思路:二分查找需要......