算法题解记录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的一些知识。

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

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

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

相关文章

贪心算法:排列算式

题目描述 给出n数字&#xff0c;对于这些数字是否存在一种计算顺序&#xff0c;使得计算过程中数字不会超过3也不会小于0&#xff1f; 输入描述: 首行给出一个正整数t,(1≤t≤1000)代表测试数据组数每组测试数据第一行一个正整数n,(1≤n≤500)第二行包含n个以空格分隔的数字…

Python+Appium自动化测试(ios+Android)

一、软件安装 安装清单&#xff1a; JDKPythonnode.jsandroid-sdk(作者通过Android Studio安装)iOS-deploybrewlibimobiledevice依赖库ideviceinstallercarthage依赖库 appium-doctor&#xff08;安装后可在命令行中通过命令:appium-doctor检查还少啥&#xff09; WebDriverAg…

ClickHouse--17--聚合函数总结

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 环境1.创建clickhouse表2.插入数据 函数(1)count&#xff1a;计算行数(2)min&#xff1a;计算最小值(3)max&#xff1a;计算最大值(4)sum&#xff1a;计算总和&…

基于SpringBoot和Vue的企业客户管理系统

今天要和大家聊的是基于SpringBoot和Vue的企业客户管理系统 &#xff01;&#xff01;&#xff01; 有需要的小伙伴可以通过文章末尾名片咨询我哦&#xff01;&#xff01;&#xff01; &#x1f495;&#x1f495;作者&#xff1a;李同学 &#x1f495;&#x1f495;个人简介…

2024年认证杯A题保暖纤维的保暖能力完整思路代码论文讲解与分析

保暖纤维的保暖能力建模 摘要 本文针对保暖纤维的保暖能力建模问题进行了深入研究。首先,文章指出现有的一些保暖性能指标,如热导率、热阻值、CLO值等,存在一些局限性,无法全面反映保暖材料的实际保暖性能。因此,本文提出了建立一个更加完善的保暖能力评价指标体系,包括热传导…

MySQL进阶一

目录 1.使用环境 2.条件判断 2.1.case when 2.2.if 3.窗口函数 3.1.排序函数 3.2.聚合函数 ​​​​​​​3.3.partiton by ​​​​​​​3.4.order by 4.待续 1.使用环境 数据库&#xff1a;MySQL 8.0.30 客户端&#xff1a;Navicat 15.0.12 2.条件判断 2.1.ca…

AWS游戏全球智能翻译,助力企业出海

随着全球数字化时代的到来&#xff0c;游戏行业已经成为跨越国界、语言和文化的强大力量。然而&#xff0c;要将游戏产品成功推向全球市场并确保用户体验的流畅与愉悦&#xff0c;语言障碍却是一道不可忽视的挑战。在这个多元化的世界中&#xff0c;如何解决语言障碍&#xff0…

视频知识整理

1 视频播放器原理 视频播放器播放一个互联网上的视频文件&#xff0c;需要经过以下几个步骤&#xff1a; 解协议&#xff1a;将流媒体协议的数据&#xff0c;解析为标准的相应的封装格式数据 解封装&#xff1a;将封装格式的数据&#xff0c;分离成为音频流压缩编码数据和视…

Unity之PlayableGraph实现动画的正播和倒播

内容将会持续更新&#xff0c;有错误的地方欢迎指正&#xff0c;谢谢! Unity之PlayableGraph实现动画的正播和倒播 TechX 坚持将创新的科技带给世界&#xff01; 拥有更好的学习体验 —— 不断努力&#xff0c;不断进步&#xff0c;不断探索 TechX —— 心探索、心进取&am…

Java基于微信小程序的在线投稿小程序(V2.0),附源码

博主介绍&#xff1a;✌IT徐师兄、7年大厂程序员经历。全网粉丝15W、csdn博客专家、掘金/华为云//InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;&#x1f3…

深入浅出 -- 系统架构之日均亿级吞吐量的网关架构(DNS轮询解析)

在前篇关于《Nginx》的文章中曾经提到&#xff1a;单节点的Nginx在经过调优后&#xff0c;可承载5W左右的并发量&#xff0c;同时为确保Nginx的高可用&#xff0c;在文中也结合了Keepalived对其实现了程序宕机重启、主机下线从机顶替等功能。 但就算实现了高可用的Nginx依旧存在…

vivado 在硬件中调试逻辑设计

在硬件中调试逻辑设计 设计中包含调试核后 &#xff0c; 您可使用运行时间逻辑分析器功能来对硬件中的设计进行调试。 使用 Vivado Logic Analyzer 进行设计调试 Vivado Logic Analyzer 功能可用于与设计中运行的新 ILA 、 VIO 和 JTAG-to-AXI Master 调试核进行交互。…

LRU缓存结构【C语言】

#include <stdio.h> #include <stdlib.h>//双链表节点结构 typedef struct Node {int key;int value;struct Node* pre;struct Node* next; } Node;//LRU结构 typedef struct {int capacity;struct Node* head;struct Node* tail;struct Node** cache; }LRUCache;…

TCP/IP 协议栈在 Linux 内核中的 运行时序分析

1、Linux内核概述 1.1 Linux内核结构 一个完整的Linux内核一般由5部分组成&#xff0c;它们分别是内存管理、进程管理、进程间通信、bai虚拟文件系统和网络接口。 1、内存管理 内存管理主要完成的是如何合理有效地管理整个系统的物理内存&#xff0c;同时快速响应内核各个子…

顶顶通呼叫中心中间件(mod_cti基于FreeSWITCH)-回铃音补偿

文章目录 前言联系我们解决问题操作步骤 前言 回铃音&#xff1a; 当别人打电话给你时&#xff0c;你的电话响铃了&#xff0c;而他听到的声音叫做回铃音。回铃音是被叫方向主叫方传送&#xff0c;也是彩铃功能的基础。我们平时打电话听到的“嘟 嘟 嘟 嘟”的声音&#xff0c;就…

4-云原生监控体系-Grafana-基本使用

1. 介绍 使用Grafana&#xff0c;您可以通过漂亮、灵活的仪表板创建、探索和共享所有数据。查询、可视化、提醒和理解您的数据&#xff0c;无论数据存储在何处。 图片出处&#xff1a; https://grafana.com/grafana/ 官方网站 2. 界面介绍 Connections 可以配置数据源&#x…

物联网实战--驱动篇之(七)RTC时钟(DS1302)

目录 一、RTC简介 二、DS1302介绍 三、初始化 四、字节读写 五、功能函数 一、RTC简介 实时时钟&#xff0c;简称RTC&#xff0c;这个在STM32的外设里也有&#xff0c;不过STM32F1系列的RTC实际上只有一个计数器功能&#xff0c;如果需要年月日要自己写软件计算 &#xff…

【应用】SpringBoot-自动配置原理

前言 本文简要介绍SpringBoot的自动配置原理。 本文讲述的SpringBoot版本为&#xff1a;3.1.2。 前置知识 在看原理介绍之前&#xff0c;需要知道Import注解的作用&#xff1a; 可以导入Configuration注解的配置类、声明Bean注解的bean方法&#xff1b;可以导入ImportSele…

MySQL——全文检索

不是所有的数据表都支持全文检索 MySQL支持多种底层数据库引擎&#xff0c;但是并非所有的引擎支持全文检索 &#xff0c;目前最常用引擎是是MyISAM和InnoDB&#xff1b;前者支持全文检索&#xff0c;后者不支持。 booolean模式操作符 实验&#xff1a; 表productnotes &…

LVGL9.1移植STM32F103C8T6花屏问题解决

这一次的话算是花了一下午差不多解决了一个问题&#xff0c;具体我是用 stm32f103c8t6(20k RAM, 128k Flash) 移植的LVGL库(屏幕是240x240的st7789, 因为RAM的buf不太够所以缩小了显示面积) 直接切入主题: 如果出现花屏问题&#xff0c; 这个问题出在你自定义编写的lv_set_flu…