从爬楼梯到斐波那契数列:解密数学之美

在这里插入图片描述

题目描述

我们来看看力扣的一道经典问题70. 爬楼梯

在这里插入图片描述

递归

假设n级台阶有climbStairs(n)种方法爬到楼梯顶。如果有n级台阶,如果第一次往上爬1级台阶,就会剩下n-1级台阶,这n-1级台阶就有climbStairs(n-1)种方法爬到楼梯顶;如果第一次往上爬2级台阶,就会剩下n-2级台阶,这n-2级台阶就有climbStairs(n-2)种方法爬到楼梯顶。所以有:climbStairs(n)=climbStairs(n-1)+climbStairs(n-2)。显然,climbStairs(1)=1,climbStairs(2)=2。

用递归就能轻松描述以上信息:

int climbStairs(int n) {if (n <= 2){return n;}// f(n) = f(n-1) + f(n-2)return climbStairs(n-1) + climbStairs(n-2);
}

不过这样是过不了的,因为递归中存在大量重复的计算。
在这里插入图片描述

循环

一种简单的方法是把递归改成循环。由climbStairs(n)=climbStairs(n-1)+climbStairs(n-2)可知,climbStairs(n)就是以1,2为前两项的斐波那契数列,从第三项开始,每一项都是前两项之和,所以只需要一项一项往后求就行了。

int climbStairs(int n) {if (n <= 2){return n;}int a = 1;int b = 2;int c = 0;// 第3项会进一次循环while (n-- > 2){c = a + b;a = b;b = c;}return c;
}

在这里插入图片描述

其他思路

当然,我们也有一些其他思路。比如,可以使用矩阵构建一个递推关系,如:
在这里插入图片描述

从而得到:
在这里插入图片描述
从而把问题转换成计算矩阵的幂的问题。

或者,直接使用特征根法计算出以上斐波那契数列的通项公式,即:
在这里插入图片描述
从而直接使用通项公式求解。

总结

爬楼梯问题本质上就是斐波那契数列问题。

感谢大家的阅读!

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Delphi 开发手持机(android)打印机通用开发流程(举一反三)

目录 一、场景说明 二、厂家应提供的SDK文件 三、操作步骤&#xff1a; 1. 导出Delphi需要且能使用的接口文件&#xff1a; 2. 创建FMX Delphi项目&#xff0c;将上一步生成的接口文件&#xff08;V510.Interfaces.pas&#xff09;引入: 3. 将jarsdk.jar 包加入到 libs中…

docker安装redis

拉取镜像 docker pull redis:6.0.6查看镜像 docker images查看一下镜像已经拉下来了 下载配置文件 到redis官网下载一下压缩包&#xff0c; http://www.redis.cn/download.html 解压一下&#xff0c;把这个文件准备好 然后修改redis.conf bind 127.0.0.1 # 注释掉这部分&…

浏览器的事件循环

其实在我们电脑的操作系统中&#xff0c;每一个运行的程序都会由自己的进程&#xff08;可能是一个&#xff0c;也可能有多个&#xff09;&#xff0c;浏览器就是一个程序&#xff0c;它的运行在操作系统中&#xff0c;拥有一组自己的进程&#xff08;主进程&#xff0c;渲染进…

C语言练习5(巩固提升)

C语言练习5 选择题 选择题 1&#xff0c;下面代码的结果是&#xff1a;( ) #include <stdio.h> #include <string.h> int main() {char arr[] { b, i, t };printf("%d\n", strlen(arr));return 0; }A.3 B.4 C.随机值 D.5 &#x1f4af;答案解析&#…

C++数据结构学习——栈

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、栈二、C语言实现1.声明代码2.实现增删查改代码3.测试代码 总结 前言 栈&#xff08;Stack&#xff09;是计算机科学中一种常见的数据结构&#xff0c;它是…

函数的参数传递和返回值-PHP8知识详解

本文学习的是《php8知识详解》中的《函数的参数传递和返回值》。主要包括&#xff1a;向函数传递参数值、向函数传递参数引用、函数的返回值。 1、向函数传递参数值 函数是一段封闭的程序&#xff0c;有时候&#xff0c;程序员需要向函数传递一些数据进行操作。可以接受传入参…

【Eclipse】汉化简体中文教程(官方汉化包,IDE自带软件安装功能),图文详情

目录 0.环境 1.步骤 1&#xff09;查看eclipse的版本 2&#xff09;在官网找语言包&#xff0c;并复制链接 3&#xff09;将链接复制到eclipse中 4&#xff09;汉化完成 0.环境 windows11&#xff0c;64位&#xff1b; eclipse 2021-6版本 1.步骤 思路&#xff1a;在官网找…

9个python自动化脚本,PPT批量生成缩略图、添加图片、重命名

引言 最近一番在整理资料&#xff0c;之前买的PPT资源很大很多&#xff0c;但归类并不好&#xff0c;于是一番准备把这些PPT资源重新整理一下。统计了下&#xff0c;这些PPT资源大概有2000多个&#xff0c;一共30多G&#xff0c;一个一个手动整理这个投入产出比也太低了。 作为…

咸鱼之王俱乐部网站开发

我的俱乐部 最新兑换码 *注意区分大小写&#xff0c;中间不能有空格&#xff01; APP666 HAPPY666 QQ888 QQXY888 vip666 VIP666 XY888 app666 bdvip666 douyin666 douyin777 douyin888 happy666 huhushengwei888 taptap666 周活动 宝箱周 宝箱说明 1.木质宝箱开启1个…

哈夫曼编码(C++实现)

文章目录 1. 前言2. 固定长度编码3. 哈夫曼编码4. 哈夫曼解码5. 编码特点6. 代码实现7. 总结 1. 前言 在上一篇文章中&#xff0c;介绍了 哈夫曼树的概念及其实现 。 哈夫曼树有什么用途呢&#xff1f; —— 那就是用来创建哈夫曼编码&#xff08;Huffman Coding —— 一种二…

IDEA软件安装包分享(附安装教程)

目录 一、软件简介 二、软件下载 一、软件简介 IntelliJ IDEA是一款流行的Java集成开发环境&#xff08;IDE&#xff09;&#xff0c;由捷克软件开发公司JetBrains开发。它专为Java开发人员设计&#xff0c;提供了许多高级功能和工具&#xff0c;使得开发人员能够更高效地编写…

识别图片中的文字

前言 PearOCR 是一款免费无限制网页版文字识别工具。 优点如下&#xff1a; 免费&#xff1a;完全免费&#xff0c;没有任何次数、大小限制&#xff0c;可以无限使用&#xff1b; 安全&#xff1a;全部数据本地运算&#xff0c;所有图片均不会被上传&#xff1b; 智能&#xf…

数仓--------简单了解

作者前言 &#x1f382; ✨✨✨✨✨✨&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f382; ​&#x1f382; 作者介绍&#xff1a; &#x1f382;&#x1f382; &#x1f382; &#x1f389;&#x1f389;&#x1f389…

【坑】Vue中带有__ob__: Observer的数组无法遍历的问题

控制台可以打印出数据但是渲染不出结构 解决办法&#xff1a; setTimeout(() > {Bus.$emit(shareRes, this.result.filter(item > item.id id)) }, 500)替换 Bus.$emit(shareRes, this.result.filter(item > item.id id))总结 解决和总结 好像和__ob__.Observe无…

Android 11/12 app-lint 系统Update-API时Lint检查问题

有以下两种解决方法 1. 加SupressLint注解 这种方式你可以其他博客也有 但是要每个类和方法都加上SuppressLint 太麻烦了 我才不要这样呢 2. 添加 --api-lint-ignore-prefix 参数直接跳过代码检查 1. 打开 frameworks/base/Android.bp 文件 2. 搜索找到这个字段 metalava…

简述docker映射(Mapping)和挂载(Mounting)

映射的概念&#xff1a; 将容器内的端口映射到主机的端口上&#xff0c;这样就可以通过主机的网络接口与容器内部进行通信。主机上对应端口的请求会被转发到容器内部&#xff0c;从而实现对容器内部程序的通信访问&#xff08;注意&#xff01;这里提到的容器内部的端口并不一定…

PDFPrinting.Net Crack

PDFPrinting.Net Crack 它能够轻松灵活地预测完美的打印结果以及用户文件的示例性显示。在.NET的PDF打印中&#xff0c;可以快速浏览最关键的元素。如果用户需要获得更详细的概述&#xff0c;那么他可以查看快速入门手册&#xff0c;甚至现有文档的详细概述参考。 在这种情况下…

Maven聚合项目(微服务项目)创建流程,以及pom详解

一、创建流程 1、首先创建springboot项目作为父项目 只留下pom.xml 文件&#xff0c;删除src目录及其他无用文件 2、创建子项目 子项目可以是maven项目&#xff0c;也可以是springboot项目 3、父子项目关联 4、父项目中依赖管理 <?xml version"1.0" encoding…

为什么选择elasticsearch分布式搜索引擎

文章目录 &#x1f52d;什么是elasticsearch&#x1f320;ELK技术栈&#x1f320;elasticsearch和lucene&#x1f320;为什么不是其他搜索技术&#xff1f; &#x1f320;总结 &#x1f52d;什么是elasticsearch elasticsearch是一款非常强大的开源搜索引擎&#xff0c;具备非常…

C语言之函数题

目录 1.乘法口诀表 2.交换两个整数 3.函数判断闰年 4.函数判断素数 5.计算斐波那契数 6.递归实现n的k次方 7.计算一个数的每位之和&#xff08;递归&#xff09; 8.字符串逆序&#xff08;递归实现&#xff09; 9.strlen的模拟&#xff08;递归实现&#xff09; 10.求…