[动态规划] (三) LeetCode 746. 使用最小花费爬楼梯

[动态规划] (三)LeetCode 746. 使用最小花费爬楼梯(两种解法)

文章目录

      • [动态规划] (三)LeetCode 746. 使用最小花费爬楼梯(两种解法)
        • 题目解析
        • 解题思路
          • 状态表示
          • 状态转移方程
          • 初始化和填表顺序
          • 返回值
          • 状态表示
          • 状态转移方程
          • 初始化和填表顺序
          • 返回值
        • 代码实现
        • 总结

746. 使用最小花费爬楼梯

image-20231102175300875

题目解析

(1) cost[i]数组是从i位置向上爬的费用

(2) 支付一次费用有两种选择:爬一次或者爬两次

(3) 可以从第0或1台阶开始爬

(4) 爬到顶楼需要的话费,从示例1可以看出,顶楼指的是cost.size。

解题思路

解法一:

状态表示

题目:最小花费

猜测:以i位置为结尾(大胆猜测,推导不出状态转移方程再重新猜)

dp[i]:题目+猜测= 到达i位置时的最小花费

状态转移方程

i之前或者i之后的状态,推出dp[i]

到达i有两种可能:i-1爬一步i-2爬两步

那dp[i]就是,到达i-1位置前的花费+当前位置的花费(i-1)或者是到达i-2位置前的话费+当前位置的花费(i-2)。

对它们两个取最小值即可。

dp[i] = min(cost[i-1]+dp[i-1], cost[i-2]+dp[i-2])
初始化和填表顺序

初始化:题目告诉我们,可以从0或者1位置开始,即dp[0] = dp[1] = 0。

填表顺序:避免越界,从左向右填

返回值

返回n位置即可,dp[n]

解法二:

状态表示

题目:最小花费

猜测:从i位置为起点

dp[i]:题目+猜测= 从i为起点到顶楼的最小花费

状态转移方程

以i为起点,有两种选择:到达i+1,再到顶楼或者到达i+2,再到顶楼

正好,我们的dp[i]是从i到顶楼的花费,所以

dp[i] = min(cost[i]+dp[i+1], cost[i]+dp[i+2])
初始化和填表顺序

初始化:我们要用的是i+1i+2位置的值,最后是从n-1或者n-2到顶楼

dp[n-1] = cost[n-1], dp[n-2] = cost[n-2]

填表顺序:我们这里是反着推导的,所以是从右往左填表的。

返回值

dp[i]表示的是从i位置开始到楼顶的最小花费,所以最后是返回dp[0]和dp[1]中小的那个即可。

代码实现

法一

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

image-20231102185253779

法二

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

image-20231102185357373

总结

细节:得出状态表示后,尝试推导状态转移方程。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/118613.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

RK3568平台 内存的基本概念

一.Linux的Page Cache page cache&#xff0c;又称pcache&#xff0c;其中文名称为页高速缓冲存储器&#xff0c;简称页高缓。page cache的大小为一页&#xff0c;通常为4K。在linux读写文件时&#xff0c;它用于缓存文件的逻辑内容&#xff0c;从而加快对磁盘上映像和数据的访…

致:CSGO游戏搬砖人的一封信

最近大家还在坚持操作CSGO游戏搬砖项目不&#xff1f; 这个项目虽是稳赚项目&#xff0c;但也有行情好和行情不好的时候&#xff0c;平台的大中小各种活动的举办&#xff0c;都会对我们的项目造成一定影响。行情的上下波动势必然会影响卡价的波动&#xff0c;影响选品的快慢&a…

树专题 —— 二叉搜索树和中序遍历

大家好&#xff0c;我是 方圆。我准备把树写成一个专题&#xff0c;包括二叉搜索树、前序、中序、后序遍历以及红黑树&#xff0c;我也想试试能不能将红黑树写好。 本篇是关于二叉搜索树&#xff0c;也是所有后续学习的基础&#xff0c;其中会涉及前序、中序、后序遍历&#x…

自动驾驶学习笔记(六)——Apollo安装

#Apollo开发者# 学习课程的传送门如下&#xff0c;当您也准备学习自动驾驶时&#xff0c;可以和我一同前往&#xff1a; 《自动驾驶新人之旅》免费课程—> 传送门 《2023星火培训【感知专项营】》免费课程—>传送门 文章目录 前言 Apollo安装 硬件配置 安装Ubuntu…

代码随想录第四十四天 | 动态规划 完全背包:纯完全背包理论基础(卡码网第52题);应用(注意遍历顺序):组合(518),排列(377)

1、动态规划&#xff1a;完全背包理论基础 有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]&#xff0c;得到的价值是value[i] 。每件物品都有无限个&#xff08;也就是可以放入背包多次&#xff09;&#xff0c;求解将哪些物品装入背包里物品价值总和最大…

Mysql数据库 9.SQL语言 查询语句 连接查询、子查询

连接查询 通过查询多张表&#xff0c;用连接查询进行多表联合查询 关键字&#xff1a;inner join 内连接 left join 左连接 right join 右连接 数据准备 创建新的数据库&#xff1a;create database 数据库名; create database db_test2; 使用数据库&#xff1a;use 数据…

Day1 ARM基础

【ARM课程认知】 1.ARM课程的作用 承上启下 基础授课阶段&#xff1a;c语言、数据结构、linux嵌入式应用层课程&#xff1a;IO、进程线程、网络编程嵌入式底层课程&#xff1a;ARM体系结构、系统移植、linux设备驱动c/QT 2.ARM课程需要掌握的内容 自己能够实现简单的汇编编…

AI 绘画 | Stable Diffusion 图生图

图生图简介 Stable Diffusion 不仅可以文生图&#xff0c;还可以图生图。文生图就是完全用提示词文本去生成我们想要图片&#xff0c;但是很多时候会有词不达意的感觉。就像我们房子装修一样&#xff0c;我们只是通过文字描述很难表达出准确的想要的装修效果&#xff0c;如果能…

AD9371 官方例程裸机SW 和 HDL配置概述(二)

AD9371 系列快速入口 AD9371ZCU102 移植到 ZCU106 &#xff1a; AD9371 官方例程构建及单音信号收发 ad9371_tx_jesd -->util_ad9371_xcvr接口映射&#xff1a; AD9371 官方例程之 tx_jesd 与 xcvr接口映射 AD9371 官方例程 时钟间的关系与生成 &#xff1a; AD9371 官方…

stm32f103+HC-SR04+ssd1306实现超声波测距

&#x1f64c;秋名山码民的主页 &#x1f602;oi退役选手&#xff0c;Java、大数据、单片机、IoT均有所涉猎&#xff0c;热爱技术&#xff0c;技术无罪 &#x1f389;欢迎关注&#x1f50e;点赞&#x1f44d;收藏⭐️留言&#x1f4dd; 获取源码&#xff0c;添加WX 目录 前言HC…

Python自动化测试(1)-自动化测试及基本技术手段概述

生产力概述 在如今以google为首的互联网时代&#xff0c;软件的开发和生产模式都已经发生了变化&#xff0c; 在《参与感》一书提到&#xff1a;某位从微软出来的工程师很困惑&#xff0c;微软在google还有facebook这些公司发展的时候&#xff0c;为何为感觉没法有效还击&…

Spring:常见的面试题和答案

1、什么是 Spring 框架&#xff1f;Spring 框架有哪些主要模块&#xff1f; Spring 框架是一个为 Java 应用程序的开发提供了综合、广泛的基础性支持的 Java 平台。 Spring 帮助开发者解决了开发中基础性的问题&#xff0c;使得开发人员可以专注于应用程序的开发。 Spring 框架…

【MogDB/openGauss的三种函数稳定性关键字】

一、ORACLE中的类似的函数稳定性关键字&#xff08;DETERMINISTIC&#xff09; 在ORACLE里&#xff0c;function有着一个DETERMINISTIC参数&#xff0c;它表示一个函数在输入不变的情况下输出是否确定&#xff0c;只要输入的参数一样&#xff0c;返回的结果一定一样的&#xf…

MS35657步进电机驱动器可兼容DRV8824

MS35657 是一款双通道 DMOS 全桥驱动器&#xff0c;可以驱动一个步进电机或者两个直流电机。可兼容DRV8824&#xff08;功能基本一致&#xff0c;管脚不兼容&#xff09;。每个全桥的驱动电流在 24V 电源下可以工作到 1.4A。MS35657 集成了固定关断时间的 PWM 电流校正器&#…

STM8单片机在医疗设备中的应用和优势

STM8单片机作为一种高性能、低功耗的微控制器&#xff0c;在医疗设备领域得到了广泛的应用。本文对STM8单片机在医疗设备中的应用进行了研究&#xff0c;探讨了它在医疗设备中的优势和特点&#xff0c;并分析了其在提升医疗设备性能、精确控制和数据处理等方面的应用效果。 一…

Arrays.asList() 和 List.of() 的列表之争

1. 概述 有时在Java中&#xff0c;为了方便&#xff0c;我们需要创建一个小列表或将数组转换为列表。Java 为此提供了一些辅助方法。 在本文中&#xff0c;我们将比较初始化小型临时数组的两种主要方法&#xff1a;List.of()和 Array.asList()。 2. Arrays.asList() Java 自…

Java前后端分离的在线考试系统源码

Java前后端分离的在线考试系统源码 技术栈 1&#xff0c;SpringBoot 2&#xff0c;Mybatis-plus 3&#xff0c;MySQL 5.7 4&#xff0c;Vue全家桶 5&#xff0c;ElementUI 6&#xff0c;Redis 7&#xff0c;Swagger 8&#xff0c;阿里云OSS 9&#xff0c;Log4j 考…

Python模块导入出现ModuleNotFoundError: No module named ‘***’解决方法

概述 几年没弄python了&#xff0c;全部还会给老师&#xff0c;今天弄了个demo&#xff0c;老是报错&#xff0c;在此记录下&#xff0c;方便后续查阅。 环境&#xff1a;Windows10 开发IDEA&#xff1a;PyCharm 2023.1.3 1、报错如下所示 2、解决方法&#xff1a;安装execjs…

RLHF的替代算法之DPO原理解析:从Zephyr的DPO到Claude的RAILF

前言 本文的成就是一个点顺着一个点而来的&#xff0c;成文过程颇有意思 首先&#xff0c;如上文所说&#xff0c;我司正在做三大LLM项目&#xff0c;其中一个是论文审稿GPT第二版&#xff0c;在模型选型的时候&#xff0c;关注到了Mistral 7B(其背后的公司Mistral AI号称欧洲…

【技术干货】开源库 Com.Gitusme.Net.Extensiones.Core 的使用

目录 1、项目介绍 2、为项目添加依赖 3、代码中导入命名空间 4、代码中使用 示例 1&#xff1a;string转换 示例 2&#xff1a;object转换 1、项目介绍 Com.Gitusme.Net.Extensiones.Core是一个.Net扩展库。当前最新版本1.0.4&#xff0c;提供了常见类型转换&#xff0c…