【第37天】斐波那契数列与爬楼梯 | 迭代的鼻祖,递推与记忆化
学习指引
- 序、专栏前言
- 一、递推与记忆化
- 二、【例题1】
- 1、题目描述
- 2、解题思路
- 3、模板代码
- 4、代码解析
- 5.原题链接
- 三、【例题1】
- 1、题目描述
- 2.解题思路
- 3、模板代码
- 4、代码解析
- 5、原题链接
- 三、推荐专栏
- 四、课后习题
序、专栏前言
本专栏开启,目的在于帮助大家更好的掌握学习Java,特别是一些Java学习者难以在网上找到系统地算法学习资料帮助自身入门算法,同时对于专栏内的内容有任何疑问都可在文章末尾添加我的微信给你进行一对一的讲解。
但最最主要的还是需要独立思考,对于本专栏的所有内容,能够进行完全掌握,自己完完全全将代码写过一遍,对于算法入门肯定是没有问题的。
算法的学习肯定不能缺少总结,这里我推荐大家可以到高校算法社区将学过的知识进行打卡,以此来进行巩固以及复习。
学好算法的唯一途径那一定是题海战略,大量练习的堆积才能练就一身本领。专栏的任何题目我将会从【题目描述】【解题思路】【模板代码】【代码解析】等四板块进行讲解。
一、递推与记忆化
在算法的学习中,有许多的题目需要我们递推得到答案,这需要我们去发掘出递推式子得到答案。就好比我们在一个有向图上想要到达终点,需要从起点一步步找到终点,所以相邻的点之间一定会有着某种关联,这种关联就是我们的递推式。斐波那契数列和爬楼梯两道题可以说是所有递推入门的经典题目,同时递推思想也可以看作是最简单动态规划思想。当然在递推时,为了减少重复计算,我们还用叫做记忆化的优化方法,可以帮我们节省大量的时间。
二、【例题1】
1、题目描述
写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项(即 F(N))。斐波那契数列的定义如下:
F(0) = 0, F(1) = 1F(N) = F(N - 1) + F(N - 2), 其中 N > 1.- 斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。
2、解题思路
核心在于递推式:F(N)=F(N−1)+F(N−2)F(N) = F(N - 1) + F(N - 2)F(N)=F(N−1)+F(N−2)
显然式子含义为每个数为前两个数之和,我们根据式子递推即可。
3、模板代码
超时代码:
class Solution {public int fib(int n) {return f(n);}int f(int x){if(x==1) return 1;if(x==0) return 0;return (f(x-1)+f(x-2))%1000000007;}
}
递归记忆化代码:
class Solution {int[] a=new int[110];public int fib(int n) {Arrays.fill(a,-1);a[0]=0;a[1]=1;dfs(n);return a[n];}int dfs(int x){if(a[x]!=-1) return a[x];return a[x]=(dfs(x-1)+dfs(x-2))%1000000007;}
}
递推代码:
class Solution {public int fib(int n) {if(n==0) return 0;int[] f=new int[n+1];f[0]=0;f[1]=1;for(int i=2;i<=n;++i){f[i]=(f[i-1]+f[i-2])%1000000007;}return f[n];}
}
4、代码解析
显然,无论是递推还是记忆化代码,我们都需要使用数组记录答案,否则当我们求解 f(n)f(n)f(n)时,本来我们已经计算出了f(n−1)f(n-1)f(n−1)和f(n−2)f(n-2)f(n−2),结果又得重新计算一次,从而导致计算量变大超时。可以直接使用数组递推时,其本身就有记忆化功能,如果使用递归来进行 dpdpdp,则大家最好加上记忆化。
5.原题链接
斐波那契数列
三、【例题1】
1、题目描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
2.解题思路
定义 f(n)f(n)f(n)为走到第 nnn 阶楼梯有多少种走法,显然第 nnn 阶只能从第 n−1n-1n−1 或者 n−2n-2n−2 阶走过来,于是我们得到递推式:
f(n)=f(n−1)+f(n−2)f(n) = f(n - 1) + f(n - 2)f(n)=f(n−1)+f(n−2)
(惊喜发现这不是和斐波那契数列一样的吗哈哈哈,那么题目迎刃而解啦,但是注意初始化有略微区别
3、模板代码
递推代码:
class Solution {public int climbStairs(int n) {int[] f=new int[n+1];if(n==1) return 1;f[1]=1;f[2]=2;for(int i=3;i<=n;++i){f[i]=f[i-1]+f[i-2];}return f[n];}
}
递推记忆化代码:
class Solution {int[] f=new int[50];public int climbStairs(int n) {Arrays.fill(f,-1);if(n==1) return 1;f[1]=1;f[2]=2;dfs(n);return f[n];}int dfs(int x){if(f[x]!=-1) return f[x];return f[x]=dfs(x-1)+dfs(x-2);}
}
4、代码解析
注意到爬楼梯和斐波那契初始化不同,递推式相同。
5、原题链接
爬楼梯

三、推荐专栏
四、课后习题
| 序号 | 题目链接 | 难度评级 |
|---|---|---|
| 1 | 使用最小花费爬楼梯 | 1 |
相关文章:
【第37天】斐波那契数列与爬楼梯 | 迭代的鼻祖,递推与记忆化
本文已收录于专栏🌸《Java入门一百例》🌸学习指引序、专栏前言一、递推与记忆化二、【例题1】1、题目描述2、解题思路3、模板代码4、代码解析5.原题链接三、【例题1】1、题目描述2.解题思路3、模板代码4、代码解析5、原题链接三、推荐专栏四、课后习题序…...
Map集合
Map集合 Map接口的简介 Map用于保存具有映射关系的数据,Map里保存着两组数据:key和value,它们都可以使任何引用类型的数据,但key不能重复。所以通过指定的key就可以取出对应的value。 Map 没有继承 Collection 接口,…...
PyQt5编程扩展 3.2 资源文件的使用
目录 本例运行效果: 设计Qt窗体 建立项目 放一个Group Box 放三个Label 放一个Horizontal Slider 放两个Line Edit 层次结构 布局 放一个Group Box 放两个Label 放两个Line Edit 放一个Push Button 层次结构 布局 放一个frame 层次结构 布局 窗体…...
Linux系统之文件共享目录设置方法
Linux系统之文件共享目录设置方法一、本次实践目的二、检查本地系统环境1.检查系统版本2.检查系统内核三、创建相关用户及用户组1.创建共享目录2.创建测试用户账号3.创建用户组4.设置用户的属组5.查看admin和IT用户组成员6.查看所有用户信息四、共享目录权限设置1.设置/data/so…...
上海亚商投顾:三大指数均涨超1% 芯片板块集体大涨
上海亚商投顾前言:无惧大盘涨跌,解密龙虎榜资金,跟踪一线游资和机构资金动向,识别短期热点和强势个股。市场情绪三大指数今日低开高走,午后集体涨超1%,创业板指盘中涨超1.7%。芯片板块集体大涨,…...
Harbor私有仓库部署与管理
目录 前言 一、Harbor概述 二、Harbor 的特性 三、Harbor的构成 四、Harbor构建Docker私有仓库 1、环境配置 2、案例需求 3、部署Harbor服务 3.1、部署docker compose服务 3.2 下载或上传Harbor安装程序 3.3、启动Harbor 3.4、查看Harbor启动镜像 4、物理机访问se…...
互联网架构之 “高可用” 详解
一、什么是高可用 高可用HA(High Availability)是分布式系统架构设计中必须考虑的因素之一,它通常是指,通过设计减少系统不能提供服务的时间。 假设系统一直能够提供服务,我们说系统的可用性是100%。 如果系统每运行…...
分布式高级篇4 —— 商城业务(2)
一、订单服务1、订单基本概念2、订单基本构成3、订单状态4、订单流程5、配置拦截器拦截订单请求6、订单确认页模型抽取7、订单确认页vo封装8、Feign 远程调用请求头丢失问题\*\*\*\*\* 惨痛教训9、Feign 异步调用请求头丢失问题10、查看库存状态11、模拟计算运费12、接口幂等性…...
二分查找基本原理
二分查找基本原理1.二分查找1.1 基本概念1.2 二分查找查找步骤1.2.1 中间索引不能整除,取整数作为中间索引1.2.2 索引不能整除,整数1作为中间索引1.3 二分查找大O记法表示2. 二分查找代码实现1.二分查找 1.1 基本概念 二分法(折半查找)是一…...
【Python实战案例】Python3网络爬虫:“可惜你不看火影,也不明白这个视频的分量......”m3u8视频下载,那些事儿~
前言 哈喽!上午好嘞,各位小可爱们!有没有等着急了呀~ 由于最近一直在学习新的内容,所以耽搁了一下下,抱歉.jpg 双手合十。 所有文章完整的素材源码都在👇👇 粉丝白嫖源码福利,请移…...
UE4:使用样条生成随机路径,并使物体沿着路径行走
一、关于样条的相关知识 参考自:样条函数 - 馒头and花卷 - 博客园 三次样条(cubic spline)插值 - 知乎 B-Spline(三)样条曲线的性质 - Fun With GeometryFun With Geometry 个人理解的也不是非常深,但是大概要知道的就是样条具…...
计算机组成原理(判断题)
计算机控制器是根据事先编好的程序,根据其指令来进行控制只会每一步骤的操作; 面向主存的双总线结构计算机系统,因在CPU与主存之间增加了一组存储器总线,由于通过存储器总线访存,提高了CPU的访存速度,也减轻…...
error: failed to push some refs to ... 就这篇,一定帮你解决
目录 一、问题产生原因 二、解决办法 三、如果还是出问题,怎么办?(必杀) 一、问题产生原因 当你直接在github上在线修改了代码,或者是直接向某个库中添加文件,但是没有对本地库同步,接着你想…...
DAMA数据管理知识体系指南之数据仓库和商务智能管理
第9章 数据仓库和商务智能管理 9.1简介 数据仓库(Data Warehouse,DW)由两个主要部分构成:首先是一个整合的决策支持数据库,其次是用于收集、清洗、转换、存储来自于各种操作型数据源和外部数据源数据的相关软件程序。两者结合以支持历史的、…...
PHP的五种常见设计模式
工厂模式 最初在设计模式 一书中,许多设计模式都鼓励使用松散耦合。要理解这个概念,让我们最好谈一下许多开发人员从事大型系统的艰苦历程。在更改一个代码片段时,就会发生问题,系统其他部分 —— 您曾认为完全不相关的部分中也有…...
教你搞懂线段树,从基础到提高
秋名山码民的主页 🎉欢迎关注🔎点赞👍收藏⭐️留言📝 🙏作者水平有限,如发现错误,还请私信或者评论区留言! 目录前言线段树逻辑概念线段树的俩个重要用处代码实现线段树题目巩固最后…...
C语言进阶——自定义类型:结构体
🌇个人主页:_麦麦_ 📚今日名言:生活不可能像你想象的那么好,也不会像你想象的那么糟。——莫泊桑《羊脂球》 目录 一、前言 二、正文 1结构体 1.1结构体的基础知识 1.2结构的声明 1.3特殊的声明 1.4结构体变量的…...
SpringSecurity学习笔记01
目录 一、课程介绍 二、框架概述 三、入门案例 四、基本原理(过滤器链) 五、基本原理(过滤器加载过程) 六、基本原理(两个重要的接口) 七、web权限方案-用户认证(设置用户名密码上) 八、…...
Python语言零基础入门教程(十一)
Python 列表(List) 序列是Python中最基本的数据结构。序列中的每个元素都分配一个数字 - 它的位置,或索引,第一个索引是0,第二个索引是1,依此类推。 Python有6个序列的内置类型,但最常见的是列表和元组。 序列都可以…...
现货白银基础知识
任何活动,任何项目,任何工作都离不开基础知识,这是肯定的。万丈高楼平地起,要想要简称百层高楼,首先得把低级打好!现货白银投资也是一样的道理,现在我们就来一起聊聊现货白银基础知识的问题&…...
深度学习在微纳光子学中的应用
深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向: 逆向设计 通过神经网络快速预测微纳结构的光学响应,替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...
AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
Chapter03-Authentication vulnerabilities
文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...
《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》
引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...
中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试
作者:Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位:中南大学地球科学与信息物理学院论文标题:BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接:https://arxiv.…...
P3 QT项目----记事本(3.8)
3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序
一、开发环境准备 工具安装: 下载安装DevEco Studio 4.0(支持HarmonyOS 5)配置HarmonyOS SDK 5.0确保Node.js版本≥14 项目初始化: ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...
【配置 YOLOX 用于按目录分类的图片数据集】
现在的图标点选越来越多,如何一步解决,采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集(每个目录代表一个类别,目录下是该类别的所有图片),你需要进行以下配置步骤&#x…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?
在大数据处理领域,Hive 作为 Hadoop 生态中重要的数据仓库工具,其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式,很多开发者常常陷入选择困境。本文将从底…...
