算法题解记录8+++爬楼梯(百日筑基)

2024-04-12 14:36

本文主要是介绍算法题解记录8+++爬楼梯(百日筑基),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述:

        假设你正在爬楼梯。需要 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

解题准备:

        1.猜测该题可能涉及的基础操作:目前看不出来。

        2.拿特殊的题目尝试一下:

                可以发现,第一层台阶非常特殊,虽然题目提供两种操作,但是我们只能爬1步,因此只有1种方案。

            3.筛查题目条件:题目仅一个输入,表示有几层台阶。其为我们提供两个操作,一次爬升一楼,或一次爬升两楼。

            4.理解:假设我们想爬第n层台阶,要不从n-1层开始爬,要不从n-2层开始爬【除了n=1的情况,题目提供n>=1】

            5.猜测:由此可以猜测,想知道第n层台阶有几种爬法,极大可能和n-2,n-1这两层台阶有关。

解题难点1分析:

        虽然猜测n层台阶与n-1、n-2可能有关系,但是未证实,其难点,是找到关系内容。

        1:如何找到三者的关系?

                我们的目标是,找到爬n层的所有方案(虽然只要求给出方案的数目),假设采用穷举法。

                假设num【x】表示爬第x层的所有方案数目。(使x>2)【以下的所有数据,默认不超出限制】

                当n=x时,x-1到x,是一种方案,x-2到x,也是一种方案。忽略其它,单单最后一步,一共有两种方案。

                面对x-1,x-3到x-1可以走2步,x-2到x-1可以走1步。同样是两种方案。

                如果爬到x-1和x-2的所有方案num【x-1】和num【x-2】,之间没有重复的序列,就可以证明num【x】=num【x-1】+num【x-2】。

        2:如何证明:x-1和x-2,之间一定不存在重复?

                对于x-1,1st.如果x-1是从x-3直接跳到x-1,那么掠过x-2,不存在重复。【x-3到达x-2也是一个步骤】

                2nd.如果x-1,从x-2爬升到x-1,那么由于x-2到x-1多一步骤,故不重复。

至此证明完毕。

递归代码:

class Solution {public int climbStairs(int n) {if(n==1){return 1;}int[] data=new int[n];data[0]=1;data[1]=2;return helper(n-1, data);}private int helper(int temp, int[] data){if(temp==1){return 2;}else if(temp==0){return 1;}if(data[temp-1]>0&&data[temp-2]>0){return data[temp-1]+data[temp-2];}else if(data[temp-2]>0){return helper(temp-1, data)+data[temp-2];}else if(data[temp-1]>0){return helper(temp-2, data)+data[temp-1];}data[temp]=helper(temp-1, data)+helper(temp-2, data);return data[temp];}
}

以上内容即我想分享的关于力扣热题8的一些知识。

        我是蚊子码农,如有补充,欢迎在评论区留言。个人也是初学者,知识体系可能没有那么完善,希望各位多多指正,谢谢大家。

这篇关于算法题解记录8+++爬楼梯(百日筑基)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

国内环境搭建私有知识问答库踩坑记录(ollama+deepseek+ragflow)

《国内环境搭建私有知识问答库踩坑记录(ollama+deepseek+ragflow)》本文给大家利用deepseek模型搭建私有知识问答库的详细步骤和遇到的问题及解决办法,感兴趣的朋友一起看看吧... 目录1. 第1步大家在安装完ollama后,需要到系统环境变量中添加两个变量2. 第3步 “在cmd中

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

Spring Retry 实现乐观锁重试实践记录

《SpringRetry实现乐观锁重试实践记录》本文介绍了在秒杀商品SKU表中使用乐观锁和MybatisPlus配置乐观锁的方法,并分析了测试环境和生产环境的隔离级别对乐观锁的影响,通过简单验证,... 目录一、场景分析 二、简单验证 2.1、可重复读 2.2、读已提交 三、最佳实践 3.1、配置重试模板

在 Spring Boot 中使用异步线程时的 HttpServletRequest 复用问题记录

《在SpringBoot中使用异步线程时的HttpServletRequest复用问题记录》文章讨论了在SpringBoot中使用异步线程时,由于HttpServletRequest复用导致... 目录一、问题描述:异步线程操作导致请求复用时 Cookie 解析失败1. 场景背景2. 问题根源二、问题详细分

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

关于Spring @Bean 相同加载顺序不同结果不同的问题记录

《关于Spring@Bean相同加载顺序不同结果不同的问题记录》本文主要探讨了在Spring5.1.3.RELEASE版本下,当有两个全注解类定义相同类型的Bean时,由于加载顺序不同,最终生成的... 目录问题说明测试输出1测试输出2@Bean注解的BeanDefiChina编程nition加入时机总结问题说明

将sqlserver数据迁移到mysql的详细步骤记录

《将sqlserver数据迁移到mysql的详细步骤记录》:本文主要介绍将SQLServer数据迁移到MySQL的步骤,包括导出数据、转换数据格式和导入数据,通过示例和工具说明,帮助大家顺利完成... 目录前言一、导出SQL Server 数据二、转换数据格式为mysql兼容格式三、导入数据到MySQL数据

关于rpc长连接与短连接的思考记录

《关于rpc长连接与短连接的思考记录》文章总结了RPC项目中长连接和短连接的处理方式,包括RPC和HTTP的长连接与短连接的区别、TCP的保活机制、客户端与服务器的连接模式及其利弊分析,文章强调了在实... 目录rpc项目中的长连接与短连接的思考什么是rpc项目中的长连接和短连接与tcp和http的长连接短

Oracle查询优化之高效实现仅查询前10条记录的方法与实践

《Oracle查询优化之高效实现仅查询前10条记录的方法与实践》:本文主要介绍Oracle查询优化之高效实现仅查询前10条记录的相关资料,包括使用ROWNUM、ROW_NUMBER()函数、FET... 目录1. 使用 ROWNUM 查询2. 使用 ROW_NUMBER() 函数3. 使用 FETCH FI