当前位置: 首页 > news >正文

9.2爬楼梯(LC70-E)

算法:

多举几个例子,找规律:

爬到第一层楼梯有一种方法,爬到二层楼梯有两种方法。

那么第一层楼梯再跨两步就到第三层 ,第二层楼梯再跨一步就到第三层(时序)。

所以到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来,那么就可以想到动态规划了。

动规五部曲:

1.确定dp数组以及下标的含义

dp[i]: 爬到第i层楼梯,有dp[i]种方

2.确定递推公式(实在不行,多举几个例子推导一下)

从dp[i]的定义可以看出,dp[i] 可以有两个方向推出来(题目中说,每次可以爬1/2个阶梯)。

首先是dp[i - 1],上i-1层楼梯,有dp[i - 1]种方法,那么再一步跳一个台阶不就是dp[i]了么(dp[i - 1]种方法)。

还有就是dp[i - 2],上i-2层楼梯,有dp[i - 2]种方法,那么再一步跳两个台阶不就是dp[i]了么(dp[i - 2]种方法)。

那么dp[i]就是 dp[i - 1]与dp[i - 2]之和!

dp[i] = dp[i - 1] + dp[i - 2] 。

3.dp数组如何初始化

题目中说了n从1开始

dp[1] = 1,dp[2] = 2

然后从i = 3开始递推

4.确定遍历顺序

从递推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出,遍历顺序一定是从前向后遍历的

5.举例推导dp数组(主要用于debug)

当n为5的时候,dp table(dp数组)应该是这样的

如果代码出问题了,就把dp table 打印出来,看看究竟是不是和自己推导的一样。

正确代码:

class Solution {public int climbStairs(int n) {int[] dp = new int[n+1];if (n<=2){return n;}dp[1] = 1;dp[2] = 2;for (int i=3 ;i<=n; i++){dp[i] = dp[i-1] +dp[i-2];}return dp[n];}
}

时间空间复杂度:

  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

相关文章:

9.2爬楼梯(LC70-E)

算法&#xff1a; 多举几个例子&#xff0c;找规律&#xff1a; 爬到第一层楼梯有一种方法&#xff0c;爬到二层楼梯有两种方法。 那么第一层楼梯再跨两步就到第三层 &#xff0c;第二层楼梯再跨一步就到第三层&#xff08;时序&#xff09;。 所以到第三层楼梯的状态可以由…...

Asp.net移除Server, X-Powered-By, 和X-AspNet-Version头

移除X-AspNet-Version很简单,只需要在Web.config中增加这个配置节: <httpRuntime enableVersionHeader"false" />移除Server在Global.asax文件总增加&#xff1a; //隐藏IIS版本 protected void Application_PreSendRequestHeaders() {HttpContext.Current.Res…...

reactnative 调用原生ui组件

reactnative 调用原生ui组件 ![组件对应关系](https://img-blog.csdnimg.cn/direct/c4351ad7bd38411e9c13087f1059a4b0.png)1.该样例已textView&#xff0c;介绍。 新建MyTextViewManager 文件&#xff0c;继承SimpleViewManager。import android.graphics.Color; import andr…...

面试手写第五期

文章目录 一. 实现一个函数用来对 URL 的 querystring 进行编码二. 如何实现一个数组洗牌函数 shuffle三. 异步加法的几种方式四. 实现trim函数五. 求多个数组的交集六. 手写实现render函数七. 驼峰转- -转驼峰八. instanceof实现九. 组合问题十. 字符串分组 一. 实现一个函数用…...

【CSS】css选择器和css获取第n个元素(:nth-of-type(n)、:nth-child(n)、first-child和last-child)

:nth-of-type、:nth-child的区别 一、css选择器二、:nth-of-type、:nth-child的区别:nth-of-type(n)&#xff1a;选择器匹配属于父元素的特定类型的第N个子元素:nth-child(n)&#xff1a;选择器匹配属于其父元素的第 N 个子元素&#xff0c;不论元素的类型:first-child&#xf…...

解析Excel文件内容,按每列首行元素名打印出某个字符串的统计占比(超详细)

目录 1.示例&#xff1a; 1.1 实现代码1&#xff1a;列数为常量 运行结果&#xff1a; 1.2 实现代码2&#xff1a;列数为变量 运行结果&#xff1a; 1.示例&#xff1a; 开发需求&#xff1a;读取Excel文件&#xff0c;统计第3列到第5列中每列的"False"字段占…...

qt中遇到[Makfile.Debug:119:debug/app.res.o] Error 1的原因以及解决方法

当我们将项目已到本地qt环境中会出现下图的代码错误 解决方法&#xff1a;在主界面中&#xff0c;点击左边的项目栏&#xff0c;选择构建设置&#xff0c;看Shadow build下面的路径是否为中文&#xff0c;改成英文&#xff0c;或者直接将Shadow build这个 √ 去掉就行了,如图已…...

pytorch调用gpu训练的流程以及示例

首先需要确保系统上安装了CUDA支持的NVIDIA GPU和相应的驱动程序。 基本步骤如下 检查CUDA是否可用&#xff1a; 使用 torch.cuda.is_available() 来检查CUDA是否可用。 指定设备&#xff1a; 可以使用 torch.device(“cuda:0”) 来指定要使用的GPU。如果系统有多个GPU&…...

学习Android的第一天

目录 什么是 Android&#xff1f; Android 官网 Android 应用程序 Android 开发环境搭建 Android 平台架构 Android 应用程序组件 附件组件 Android 第一个程序 HelloWorld 什么是 Android&#xff1f; Android&#xff08;发音为[ˈnˌdrɔɪd]&#xff0c;非官方中文…...

回归预测 | Matlab实现CPO-LSTM【24年新算法】冠豪猪优化长短期记忆神经网络多变量回归预测

回归预测 | Matlab实现CPO-LSTM【24年新算法】冠豪猪优化长短期记忆神经网络多变量回归预测 目录 回归预测 | Matlab实现CPO-LSTM【24年新算法】冠豪猪优化长短期记忆神经网络多变量回归预测效果一览基本介绍程序设计参考资料 效果一览 基本介绍 1.Matlab实现CPO-LSTM【24年新算…...

Typora导出html文件图片自动转换成base64

Typora导出html文件图片自动转换成base64 一、出现问题二、解决方案三、编码实现3.1.创建Java项目3.2.代码3.3.打包成Jar包 四、如何使用endl 一、出现问题 typora 导出 html 的时候必须带有原图片&#xff0c;不方便交流学习&#xff0c;文件太多显得冗余&#xff0c;只有将图…...

『C++成长记』string使用指南

&#x1f525;博客主页&#xff1a;小王又困了 &#x1f4da;系列专栏&#xff1a;C &#x1f31f;人之为学&#xff0c;不日近则日退 ❤️感谢大家点赞&#x1f44d;收藏⭐评论✍️ 目录 一、string类介绍 二、string类的常用接口说明 &#x1f4d2;2.1string类对象的常…...

硬件连通性测试:构建数字世界的无形基石

在当今数字化的时代&#xff0c;硬件设备的连通性对于系统的正常运行至关重要。硬件连通性测试作为确保设备协同工作的关键步骤&#xff0c;扮演着构建数字世界的无形基石的角色。本文将深入探讨硬件连通性测试的意义、方法以及在现代科技生态系统中的重要性。 1. 硬件连通性测…...

mysql的安装与卸载

mysql的安装 mysql 8.0的安装步骤&#xff1a; 1. 从mysql官网上下载mysql安装软件 https://www.mysql.com/ 2. 双击msi文件进行安装 3. 选择安装的类型 选择server only可以远程访问数据库 4. 选择服务并安装 5. 安装中&#xff0c;安装完成后直接next 6. 进入mysql的配置 …...

假期作业 2.2

第一章 命名空间 一&#xff0e;选择题 1、编写C程序一般需经过的几个步骤依次是&#xff08; B &#xff09; A. 编辑、调试、编译、连接 B. 编辑、编译、连接、运行 C. 编译、调试、编辑、连接 D. 编译、编辑、连接、运行 2、所谓数据封装就是将一组数据和与这组数…...

运维SRE-02 正则表达式、grep

1.特殊符号补充 1.1位置相关的特殊符号 . 当前目录 .. 当前目录的上级目录 ~ 当前用户家目录 / 根目录 cd - 返回上次所在目录1.2熟练掌握 # 注释符号,root命令提示符 | 管道符号.1.3了解其他特殊符号 $ 取值(取出变量的值),普通用户的提示符 ! % ^ & * (){} [] ; ? \…...

【SpringCloud】使用OpenFeign进行微服务化改造

目录 一、需求与背景二、OpenFeign 远程调用技术原理三、项目代码演示3.1 引入依赖3.2 实现OpenFeign注解修饰接口3.3 指定 OpenFeign 远程调用接口的扫描路径 四、OpenFeign 在日志中打印Request和Response五、OpenFeign 客户端超时配置六、使用 OpenFeign 实现服务降级6.1 实…...

DRV8313和L298N都是电机驱动,一个是驱动三相FOC无刷直流电机的,一个是驱动有刷电机,使stm32控制无刷电机简单入门知识

DRV8313和L298N都是电机驱动器&#xff0c;但它们之间存在一些关键的区别&#xff1a; DRV83131&#xff1a; 由德州仪器&#xff08;TI&#xff09;制造。 具有集成的场效应晶体管&#xff08;FET&#xff09;。 最大电压为65V。 峰值电流为3A。 适用于三相电机驱动。 L298N…...

React16源码: React中event事件系统初始化源码实现

event 事件系统初始化 1 &#xff09;概述 react事件系统比较的复杂&#xff0c;它是基于dom的事件系统在dom事件系统上面进行了一个深度的封装它里面的很多实现逻辑都是自由的一套在初始化 react-dom 的源码的时候&#xff0c;会为react的事件系统注入 reactdom 相关的一些插…...

Qt6入门教程 15:QRadioButton

目录 一.简介 二.常用接口 三.实战演练 1.径向渐变 2.QSS贴图 3.开关效果 4.非互斥 一.简介 QRadioButton控件提供了一个带有文本标签的单选按钮。 QRadioButton是一个可以切换选中&#xff08;checked&#xff09;或未选中&#xff08;unchecked&#xff09;状态的选项…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)

推荐 github 项目:GeminiImageApp(图片生成方向&#xff0c;可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...

Redis:现代应用开发的高效内存数据存储利器

一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发&#xff0c;其初衷是为了满足他自己的一个项目需求&#xff0c;即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源&#xff0c;Redis凭借其简单易用、…...