(75)爬楼梯

文章目录

  • 1. 每日一言
  • 2. 题目
    • 2.1 解题思路
      • 2.1.1 递归
      • 2.1.2 记忆化搜索
      • 2.1.3 动态规划
      • 2.1.4 动态规划空间优化
    • 2.2 代码
      • 2.2.1 递归
      • 2.2.2 记忆化搜索
      • 2.2.3 动态规划
      • 2.2.4 动态规划空间优化
  • 3. 结语


1. 每日一言

Happy life lies in a peaceful mind.
幸福的生活存在于心绪的宁静之中。


2. 题目

题目链接:爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

  • 示例 1:
    输入:n = 2
    输出:2
    解释:有两种方法可以爬到楼顶。
    1. 1 阶 + 1 阶
    2. 2 阶

  • 示例 2:
    输入:n = 3
    输出:3
    解释:有三种方法可以爬到楼顶。
    1. 1 阶 + 1 阶 + 1 阶
    2. 1 阶 + 2 阶
    3. 2 阶 + 1 阶

提示:

1 <= n <= 45


2.1 解题思路

2.1.1 递归

  1. 首先,函数判断如果 n 小于等于 2,则直接返回 n。因为在楼梯阶数小于等于 2 的情况下,只有一种方式爬到顶部,即分别走一步或者直接跨两步。

  2. 对于大于 2 的情况,函数采用递归的方式进行计算。爬到第 n 阶楼梯的方式数量等于爬到第 n-1 阶和第 n-2 阶的方式数量之和。这是因为爬到第 n 阶楼梯只有两种方式,一种是从第 n-1 阶再爬一阶,另一种是从第 n-2 阶再跨两阶。

  3. 最后,将计算得到的方式数量 sum 返回。

2.1.2 记忆化搜索

  1. 首先,定义一个全局数组 men,大小为 46(因为题目中规定楼梯数不超过 45)。这个数组用来保存已经计算过的楼梯阶数对应的爬楼梯方式数量,避免重复计算。
  2. 接下来定义一个递归函数 climb(int n),用来计算爬到第 n 阶楼梯的方式数量。如果 n 小于等于 2,则直接返回 n,表示只有一种或两种方式爬到顶部。
  3. 如果 men[n] 不为 -1,说明之前已经计算过爬到第 n 阶楼梯的方式数量,直接返回 men[n]。
  4. 如果 men[n] 为 -1,说明还没有计算过爬到第 n 阶楼梯的方式数量,此时调用递归函数 climb(n-1) + climb(n-2) 来计算,并将结果保存在 men[n] 中,然后返回该结果。
  5. 最后,在 climbStairs 函数中,将 men 数组初始化为 -1,并调用 climb 函数来求解爬楼梯问题。

2.1.3 动态规划

  1. 首先,定义一个长度为 46 的整型数组 climb,用来存储爬到每个楼梯阶数的方式数量。数组初始化为 [1, 2],表示爬到第一阶和第二阶楼梯的方式数量分别为 1 和 2。
  2. 接下来,使用一个循环从第三阶楼梯开始计算爬楼梯的方式数量。对于第 i 阶楼梯,爬到这一阶的方式数量等于爬到第 i-1 阶和第 i-2 阶的方式数量之和,因为只有两种方式可以到达第 i 阶楼梯,要么是从第 i-1 阶跨一步,要么是从第 i-2 阶跨两步。
  3. 最后,返回数组 climb 中第 n-1 个元素,即爬到第 n 阶楼梯的方式数量。

2.1.4 动态规划空间优化

  1. 如果输入的楼梯阶数 n 小于等于 2,那么直接返回 n,因为在这种情况下,只有一阶或者两阶楼梯,爬到顶部的方式数量分别为 1 和 2。
  2. 对于大于 2 的情况,定义三个变量 a、b 和 c,分别表示爬到第 n-2、第 n-1 和第 n 阶楼梯的方式数量。初始时,a 被赋值为 1(表示爬到第一阶楼梯的方式数量),b 被赋值为 2(表示爬到第二阶楼梯的方式数量)。
  3. 使用一个循环来计算爬到第 n 阶楼梯的方式数量。循环从第 3 阶楼梯开始,依次计算爬到每一阶楼梯的方式数量,直到计算到第 n 阶为止。
  4. 在循环中,更新 c 的值为 a + b,然后将 b 的值赋给 a,将 c 的值赋给 b,以便继续下一轮循环。
  5. 循环结束后,c 中存储的就是爬到第 n 阶楼梯的方式数量。
  6. 最后,返回 c。

2.2 代码

2.2.1 递归

int climbStairs(int n) {
    if(2 >= n) {
        return n;
    }

    int sum = 0;
    sum = climbStairs(n-1) + climbStairs(n-2);
    
    return sum;
}

2.2.2 记忆化搜索

int men[46];
int climb(int n) {
    if(n <= 2) {
        return n;
    }
    if(men[n] != -1) {
        return men[n];
    }
    return men[n] = climb(n-1) + climb(n-2);;
}
int climbStairs(int n) {
    for(int i = 0; i < 46; i++) {
        men[i] = -1;
    }
    return climb(n);
}

2.2.3 动态规划

int climbStairs(int n) {
    int climb[46];
    climb[0] = 1;
    climb[1] = 2;

    for(int i = 2; i < n; i++) {
        climb[i] = climb[i-1] + climb[i-2];
    }

    return climb[n-1];
}

2.2.4 动态规划空间优化

int climbStairs(int n) {
    if(n <= 2) {
        return n;
    } else {
        int a = 1;
        int b = 2;
        int c = 0;
        while(n > 2) {
            c = a + b;
            a = b;
            b = c;
            --n;
        }
        return c;
    }
}

3. 结语

请给自己些耐心,不要急于求成。
山外青山楼外楼,莫把百尺当尽头。
保持空杯心态加油努力吧!


都看到这里啦!真棒(*^▽^*)

可以给作者一个免费的赞赞吗,这将会鼓励我继续创作,谢谢大家

编程小白写作,如有纰漏或错误,欢迎指正


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

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

相关文章

DAY16 二叉树最大深度最小深度完全二叉树节点个数

9.二叉树的最大深度 递归法 后序遍历 本题可以使用前序&#xff08;中左右&#xff09;&#xff0c;也可以使用后序遍历&#xff08;左右中&#xff09;&#xff0c;使用前序求的就是深度&#xff0c;使用后序求的是高度。 二叉树节点的深度&#xff1a;指从根节点到该节点…

安装和使用 Oracle Database 23c 容器鏡像

Oracle Database 23c 是 Oracle 最新的数据库版本&#xff0c;它带来了许多新特性和性能改进。 对于开发者来说&#xff0c;Oracle 提供了一个免费的开发者版&#xff0c; 可以通过 Docker 容器轻松安装和使用。以下是详细的安装和使用指南。 安装 Docker 在开始之前&#xff0…

FME学习之旅---day17

我们付出一些成本&#xff0c;时间的或者其他&#xff0c;最终总能收获一些什么。 【FME-HOW-TO系列】28 栅格邻域函数 RasterConvolver转换器说明&#xff1a; 接受包含栅格几何对象的输入要素&#xff0c;并在对所有波段应用卷积滤波 器后输出要素。 本人对栅格数据处理的较…

npm mongoose包下载冲突解决之道

我在新电脑下载完项目代码后,运行 npm install --registryhttps://registry.npm.taobao.org 1运行就报错&#xff1a; npm ERR! code ERESOLVE npm ERR! ERESOLVE unable to resolve dependency tree npm ERR! npm ERR! While resolving: lowcode-form-backend1.0.0 npm …

Find Any File (FAF) for Mac:您的专属文件搜索神器

在数字时代&#xff0c;我们的Mac硬盘中堆积着各式各样的文件&#xff0c;从工作文档到家庭照片&#xff0c;从音乐视频到学习资料&#xff0c;无一不体现出我们的生活和工作的丰富多彩。然而&#xff0c;当我们需要快速找到某个特定文件时&#xff0c;却常常在茫茫文件海中迷失…

送朋友的生日祝福静态页面代码!(小白也能轻松GET!)

Hey亲爱的小白们&#xff01;&#x1f44b; 知道你们想给朋友一个独特又有心的生日祝福&#xff0c;却苦于没有编程基础吗&#xff1f;别担心&#xff0c;来白嫖&#xff01;&#x1f381; &#x1f680;【生日祝福静态页面代码】来啦&#xff01;只需简单几步&#xff0c;就能…

Redis 的慢日志

Redis 的慢日志 Redis 的慢日志&#xff08;Slow Log&#xff09;是用于记录执行时间超过预设阈值的命令请求的系统。慢日志可以帮助运维人员和开发人员识别潜在的性能瓶颈&#xff0c;定位那些可能导致 Redis 性能下降或响应延迟的慢查询。以下是 Redis 慢日志的相关细节&…

【LV16 day1 自动mknod】

一、起源 仅devfs&#xff0c;导致开发不方便以及一些功能难以支持&#xff1a; 热插拔 不支持一些针对所有设备的统一操作&#xff08;如电源管理&#xff09;不能自动mknod用户查看不了设备信息设备信息硬编码&#xff0c;导致驱动代码通用性差&#xff0c;即没有分离设备和…

Web前端—(原生JS)歌词滚动效果

歌词滚动效果实现 歌词滚动效果HTML部分CSS部分JS部分解析歌词字符串&#xff0c;得到歌词的对象数组计算在当前情况下&#xff0c;播放器播放到第几秒的情况创建歌词元素设置ul元素的偏移量最后对时间变化的事件进行监听完整JS代码 歌词滚动效果 实现效果如图所示&#xff1a…

防静电工作台:静电敏感环境下的必备设备

在当今的电子制造、精密仪器制造、化学实验室等领域&#xff0c;静电敏感性已成为一个不可忽视的问题。静电可能对设备和操作人员造成严重损害&#xff0c;因此防止静电的产生和传导是至关重要的。在这样的背景下&#xff0c;防静电工作台应运而生&#xff0c;成为这些领域中不…

【蓝桥杯省赛真题37】python农田划分 中小学青少年组蓝桥杯比赛 算法思维python编程省赛真题解析

目录 python农田划分 一、题目要求 1、编程实现 2、输入输出 二、算法分析 三、程序编写 四、程序说明 五、运行结果 六、考点分析 七、 推荐资料 1、蓝桥杯比赛 2、考级资料 3、其它资料 python农田划分 第十三届蓝桥杯青少年组python比赛省赛真题 一、题目要求…

kafka学习笔记02(小滴课堂)

Kafka命令行生产者发送消息和消费者消费消息实战 已存在的kafka不能重复创建。 broker设置的是1&#xff0c;factor大于broker了&#xff0c;所以报错。 生产者发送消息&#xff1a; kafka列表出现了新的kafka。 我们使用这个kafka。 我们启动消费者&#xff1a; 我们现在不从…

【dll解密】Dll加壳保护方案分析修复

分析背景 NGame游戏海外版出现了破解版&#xff0c;该版本在dump出游戏的dll中不能直接通过反编译工具查看修改后的游戏代码&#xff0c;导致无法确定外挂修改的直接逻辑点。本文主要针对AssemblyCSharp.dll模版&#xff0c;分析其dll保护的方法。 分析过程 1、拿到Encrypt_As…

【动手学深度学习-pytorch】 9.4 双向循环神经网络

在序列学习中&#xff0c;我们以往假设的目标是&#xff1a; 在给定观测的情况下 &#xff08;例如&#xff0c;在时间序列的上下文中或在语言模型的上下文中&#xff09;&#xff0c; 对下一个输出进行建模。 虽然这是一个典型情景&#xff0c;但不是唯一的。 还可能发生什么其…

【LVGL-使用SquareLine Studio设计器 】

LVGL-使用SquareLine Studio设计器 ■ 简介■ 安装■ SquareLine Studio移植到工程 ■ 简介 SquareLine Studio 设计器是一个付费软件。 ■ 安装 SquareLine Studio 设计器的下载地址 我们点击“WINDOWS”下载 SquareLine Studio 设计器&#xff0c;下载完成之后我们就会得到…

GIS硬核入门,二维地图是如何使用WGS84坐标系来转换成墨卡托投影的xyz地图瓦片切片的详细原理

前言 二维地图一般分成两种&#xff0c;一种是简化的道路地图视图&#xff0c;一种是卫星拍摄的高清影像地图。 四种坐标概念理解&#xff1a; 经度和纬度&#xff0c;对应地球上唯一的一个点&#xff08;例如&#xff1a;Google 使用世界大地测量系统 WGS84 标准&#xff0…

Day49:WEB攻防-文件上传存储安全OSS对象分站解析安全解码还原目录执行

目录 文件-解析方案-目录执行权限&解码还原 目录执行权限 解码还原 文件-存储方案-分站存储&OSS对象 分站存储 OSS对象存储 知识点&#xff1a; 1、文件上传-安全解析方案-目录权限&解码还原 2、文件上传-安全存储方案-分站存储&OSS对象 文件-解析方案-目…

数据结构之二叉树由浅入深(四)

目录 题外话 正题 第一题 第一题思路 第一题代码详解 第二题 第二题思路 第二题代码详解 第三题 第三题思路 第三题代码及详解 第四题 第四题思路 第四题代码及详解 第五题 第五题思路 第五题代码及详解 题外话 本来昨天就想写完这篇文章,怎么样是不是很大胆?…

ttkbootstrap界面美化系列之Notebook(四)

在简单的界面设计中&#xff0c;Notebook也是常用的组件之一&#xff0c;Notebook组件的引入可以根据标签来切换不同的界面。使得界面更有层次感&#xff0c;不必都挤在一个界面上。在tkinter中就有Notebook组件&#xff0c;在ttkbootstrap中&#xff0c;同样也对Notebook进行了…

Flutter开发之objectbox

Flutter开发之objectbox 在之前进行iOS开发的时候使用WCDB去进行管理数据库很方便&#xff0c;它支持ORM&#xff08;Object-Relational Mapping&#xff0c;对象关系映射&#xff09;&#xff0c;用于实现面向对象编程语言里不同类型系统的数据之间的转换。 那么在Flutter开发…