小工具      在线工具  汉语词典  css  js  c++  java

leetcode每日一题:746.以最小成本爬楼梯

算法提炼,leetcode,算法,动态规划,蓝桥杯,数据结构 额外说明

收录于:115天前

系列:动态规划
语言:java
题目来源:Leetcode746. 使用最小花费爬楼梯
开启动态规划章节了!!欢迎您在留言和我一起完成每日打卡,以后每天8点半前发布每日一题。

题目

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

限制:

2 <= cost.length <= 1000
0 <= cost[i] <= 999

思路:

分析:动规五部曲。
1.确定dp[i]含义:到达i层所消耗的最少体力值
2.确定递推公式:题中说每次可以移动一步或者两步,所以dp[i]从他们两个中取小的值,当移动后,就会消耗相应的体力。所以此时的dp[i] = Math.min(dp[i-1],dp[i-2]);
3.初始化dp数组。dp[0] = cost[0],dp[1]=cost[1];,从题中给的信息可以看出
4.确定遍历顺序。 这里相对比较难,可以好好想一下。dp[i]是由前两个推导出来的,都是由前面的数推导出来,所以遍历顺序应该是从前往后。
5.举例推导。

代码:

class Solution {
    
    public int minCostClimbingStairs(int[] cost) {
    
        int []dp = new int[cost.length];
        dp[0] =cost[0];
        dp[1] = cost[1];
        for(int i =2;i<dp.length;i++){
    
            dp[i] = Math.min(dp[i-1],dp[i-2])+cost[i];
        }
        return Math.min(dp[cost.length-1],dp[cost.length-2]);
    }
}

感谢您的阅读,希望对您有所帮助。关注我,完成每日算法自律打卡。开始永远不会太晚! !

. . .

相关推荐

额外说明

线程池执行FutureTask并获取返回结果

一、FutureTask 一种可取消的异步计算。这个类提供了Future的基本实现,提供了启动和取消计算、查询计算是否完成以及检索计算结果的方法。只有在计算完成后才能检索结果;如果计算尚未完成,则get方法将被阻塞。一旦计算完成,就无法重新启动或取消计算

额外说明

安装python3后使用yum命令是否出错?

在CentOS中,默认情况下,自带python2.7版本环境,但是由于业务需求,将python版本升级到python3.0以上版本,在网上找了一个教程,顺利的将python3.9安装好了,但是随之而来又出现了一个问题,由于安装了python3以上版本,导

额外说明

[Visual Studio 2022] 首次安装时发生致命错误 C1083:无法打开包含文件:“crtdbg.h”:没有这样的文件或目录

VS2022 包括的版本如下: Windows版本 Windows SDK版本 Windows 10 版本 1903 Windows 10 SDK 版本 1903 (10.0.18362.1) Windows 10 版本 2004 Windows 10

额外说明

shell截取字符串

https://www.jb51.net/article/206555.htm

额外说明

AMD R3200G+华擎A320M-HDV R4.0装机鲁大师的跑分

1. 配置 2. 报价 3.总体外观 4. 显卡驱动安装前 5. 安装随主板附带的光盘中的驱动后 6. CineBench跑分

额外说明

爬虫进阶之路---Mitmproxy(PC端和移动端环境搭建——实现HTTP和HTTPS协议请求及响应信息的截取,mitmdump插件的使用及编写)

Mitmproxy 简介和安装 概念 作用 本次实现基于的原理 安装 工具介绍 设置代理 PC端设置代理 PC端安装证书——消除警告,以获取https的请求! 移动端设置代理 mitmdump 插件使用[(官网介绍!)](https://docs.mit

额外说明

HTML的笔记及展示(2)(表单元素、input元素、label、button以及HTML5新增的一些元素)

一、HTML原有的表单与表单控件 1.<form…/>元素 用于生成输入表单,该元素不会生成可视化部分。如单行文本框、多行文本框、单选按钮、复选框等都需要放在<form…/>元素内 form元素的重要属性: action:指定当单击表单内的"确认"按钮时

额外说明

【PHP面试题46】php-fpm的工作模式是什么,如何进行配置?

文章目录 一、前言 二、PHP-FPM的工作模式 三、进程数量配置依据 四、php-fpm常见的配置参数 4.1 pm.max_children 4.2 pm.start_servers 4.3 pm.min_spare_servers 4.4 pm.m

额外说明

利用Python计算积分

文章目录 一、不定积分 (一)公式 (二)示例 (三)利用Python计算不定积分 二、定积分 (一)公式 (二)示例 (三)利用Python计算定积分 (四)计算曲边形面积 一、不定积分 (一)公式 ∫ f ( x ) d x

额外说明

Spark基础学习笔记17:掌握RDD算子

文章目录 零、本讲学习目标 一、RDD算子 二、准备工作 (一)准备文件 1、准备本地系统文件 2、把文件上传到HDFS (二)启动Spark Shell 1、启动HDFS服务 2、启动Spark服务 3、启动Spark Shell 三、转化算子 (一)

ads via 小工具