力扣题解-746. 使用最小花费爬楼梯(动态规划)

2024-06-10 06:18

本文主要是介绍力扣题解-746. 使用最小花费爬楼梯(动态规划),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目:746. 使用最小花费爬楼梯

数组的每个索引作为一个阶梯,第 i个阶梯对应着一个非负数的体力花费值 costi。

每当你爬上一个阶梯你都要花费对应的体力花费值,然后你可以选择继续爬一个阶梯或者爬两个阶梯。

您需要找到达到楼层顶部的最低花费。在开始时,你可以选择从索引为 0 或 1 的元素作为初始阶梯。

示例 1:

输入: cost = [10, 15, 20]
输出: 15
解释: 最低花费是从cost[1]开始,然后走两步即可到阶梯顶,一共花费15。
示例 2:

输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出: 6
解释: 最低花费方式是从cost[0]开始,逐个经过那些1,跳过cost[3],一共花费6。
注意:

cost 的长度将会在 [2, 1000]。
每一个 cost[i] 将会是一个Integer类型,范围为 [0, 999]。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/min-cost-climbing-stairs
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

题解1

利用动态规划求解。

1. 状态定义

假设数组dp[i]表示爬到楼梯i时花费的体力值。

2. 状态转移方程

由于每次最多爬两级,因此dp[i]有两种方式到达:即从第i-1层楼梯,或从第i-2层楼梯, 则:

dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])i >= 2

3. 初始条件/边界

索引为 0 或 1 的元素作为初始阶梯时无需花费体力。

dp[0] = 0, dp[1] = 0

4. 最优解

到达楼顶为最终解dp[n]

代码1

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();vector<int> dp(n+1);dp[0] = 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

由状态转移方程,当前状态只与前两个状态dp[i-1]dp[i-2]有关,因此可用两个变量来缓存即可。

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

题解2

利用动态规划求解。

1. 状态定义

假设数组dp[i]表示爬过楼梯 i 时花费的体力值,此时dp[i]包括爬楼梯i的体力花费。

2. 状态转移方程

由于每次最多爬两级,因此dp[i]有两种方式到达:即从第i-1层楼梯,或从第i-2层楼梯, 则:

dp[i] = cost[i] + min(dp[i-1], dp[i-2])i >= 2

3. 初始条件/边界

索引为 0 或 1 的元素作为初始阶梯时无需花费体力,但需要爬过楼梯0和1时就需要花费对应的体力值。

dp[0] = cost[0], dp[1] = cost[1]

4. 最优解

爬过楼梯n-1,或爬过楼梯n-2时可以直接到达楼顶,因此最终解表示为min(dp[n-1], dp[n-2])

代码2

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

空间复杂度改进2

由状态转移方程,当前状态只与前两个状态dp[i-1]dp[i-2]有关,因此可用两个变量来缓存即可。

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

这篇关于力扣题解-746. 使用最小花费爬楼梯(动态规划)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1047410

相关文章

中文分词jieba库的使用与实景应用(一)

知识星球:https://articles.zsxq.com/id_fxvgc803qmr2.html 目录 一.定义: 精确模式(默认模式): 全模式: 搜索引擎模式: paddle 模式(基于深度学习的分词模式): 二 自定义词典 三.文本解析   调整词出现的频率 四. 关键词提取 A. 基于TF-IDF算法的关键词提取 B. 基于TextRank算法的关键词提取

使用SecondaryNameNode恢复NameNode的数据

1)需求: NameNode进程挂了并且存储的数据也丢失了,如何恢复NameNode 此种方式恢复的数据可能存在小部分数据的丢失。 2)故障模拟 (1)kill -9 NameNode进程 [lytfly@hadoop102 current]$ kill -9 19886 (2)删除NameNode存储的数据(/opt/module/hadoop-3.1.4/data/tmp/dfs/na

Hadoop数据压缩使用介绍

一、压缩原则 (1)运算密集型的Job,少用压缩 (2)IO密集型的Job,多用压缩 二、压缩算法比较 三、压缩位置选择 四、压缩参数配置 1)为了支持多种压缩/解压缩算法,Hadoop引入了编码/解码器 2)要在Hadoop中启用压缩,可以配置如下参数

Makefile简明使用教程

文章目录 规则makefile文件的基本语法:加在命令前的特殊符号:.PHONY伪目标: Makefilev1 直观写法v2 加上中间过程v3 伪目标v4 变量 make 选项-f-n-C Make 是一种流行的构建工具,常用于将源代码转换成可执行文件或者其他形式的输出文件(如库文件、文档等)。Make 可以自动化地执行编译、链接等一系列操作。 规则 makefile文件

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

使用opencv优化图片(画面变清晰)

文章目录 需求影响照片清晰度的因素 实现降噪测试代码 锐化空间锐化Unsharp Masking频率域锐化对比测试 对比度增强常用算法对比测试 需求 对图像进行优化,使其看起来更清晰,同时保持尺寸不变,通常涉及到图像处理技术如锐化、降噪、对比度增强等 影响照片清晰度的因素 影响照片清晰度的因素有很多,主要可以从以下几个方面来分析 1. 拍摄设备 相机传感器:相机传

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表

pdfmake生成pdf的使用

实际项目中有时会有根据填写的表单数据或者其他格式的数据,将数据自动填充到pdf文件中根据固定模板生成pdf文件的需求 文章目录 利用pdfmake生成pdf文件1.下载安装pdfmake第三方包2.封装生成pdf文件的共用配置3.生成pdf文件的文件模板内容4.调用方法生成pdf 利用pdfmake生成pdf文件 1.下载安装pdfmake第三方包 npm i pdfma

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合,内部除了存储元素外,还会存储一个score,存储在zset中的元素会按照score的大小升序排列,不同元素的score可以重复,score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n