当前位置: 首页 > news >正文

【青蛙跳台阶问题 —— (三种算法)】

青蛙跳台阶问题 —— (三种算法)

  • 一.题目介绍
    • 1.1.题目
    • 1.2.图示
  • 二.解题思路
  • 三.题解及其相关算法
    • 3.1.递归分治法
    • 3.2.动态规划算法(Dynamic Programming)
    • 3.3.斐波那契数列法
  • 四.注意细节

一.题目介绍

1.1.题目

一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例 1:
输入:n = 2
输出:2

示例 2:
输入:n = 7
输出:21

示例 3:
输入:n = 0
输出:1

提示:
0 <= n <= 100

1.2.图示

在这里插入图片描述

二.解题思路

此类求多少种可能性 的题目一般都有递推性质 ,即 f(n)和 f(n-1)…f(1)之间是有联系的。
设跳上 n级台阶有 f(n)种跳法。在所有跳法中,青蛙的最后一步只有两种情况: 跳上1级或 2级台阶。
当为 1级台阶: 剩 n-1个台阶,此情况共有 f(n-1)种跳法;
当为 2级台阶: 剩 n-2个台阶,此情况共有 f(n-2)种跳法。
f(n)为以上两种情况之和,即 f(n)=f(n-1)+f(n-2),以上递推性质为斐波那契数列。本题可转化为求斐波那契数列第 n项的值 ,与斐波那契数列等价,唯一的不同在于起始数字不同。
青蛙跳台阶问题: f(0)=1 , f(1)=1, f(2)=2;
斐波那契数列问题: f(0)=0 , f(1)=1, f(2)=1。

在这里插入图片描述

三.题解及其相关算法

斐波那契数列的定义是 f(n + 1) = f(n) + f(n - 1),生成第n项的做法有以下几种:

3.1.递归分治法

递归分治法:
原理: 把 f(n)问题的计算拆分成 f(n-1)和 f(n-2)两个子问题的计算,并递归,以 f(0)和 f(1)为终止条件。
缺点: 大量重复的递归计算,例如 f(n)和 f(n - 1)两者向下递归都需要计算 f(n - 2)的值。
这个程序的时间复杂度为 O(2^n),因为我们需要递归地计算从 1 到 n 的所有整数的和。在输入的楼梯数较大时,程序可能会运行超时。

#include <stdio.h>int climbStairs(int n) {int con=(int)1e9 + 7;if (n == 1) {return 1;}else if (n == 2) {return 2;}else {return climbStairs(n - 1)%con + climbStairs(n - 2)%con;}
}int main() {int n;printf("请输入楼梯的阶数:");scanf("%d", &n);int ways = climbStairs(n);printf("%d 阶楼梯一共有 %d 种跳法。\n", n, ways);return 0;
}

在这里插入图片描述

3.2.动态规划算法(Dynamic Programming)

动态规划算法(Dynamic Programming)(记忆化递归法)
动态规划: 是一种用于解决多阶段决策问题的算法,它通过将问题分解为更小的子问题,并通过存储已经解决的子问题的结果来避免重复计算。
原理: 在递归法的基础上,新建一个长度为 n的数组,用于在递归时存储 f(0)至 f(n)的数字值,重复遇到某数字时则直接从数组取用,避免了重复的递归计算。
缺点: 记忆化存储的数组需要使用 O(N)的额外空间。

#define MAX 100
int ClimbStairs(int number)
{int con = (int)1e9 + 7;if (number == 1)return 1;else if (number == 2)return 2;else{int dp[MAX];dp[1] = 1;dp[2] = 2;int i = 0;for (i = 3; i <= number; i++){dp[i] = dp[i - 1] % con + dp[i - 2] % con;}return dp[number];}
}int main() {int n;printf("请输入楼梯的阶数:");scanf("%d", &n);int ways = climbStairs(n);printf("%d 阶楼梯一共有 %d 种跳法。\n", n, ways);return 0;
}

在这里插入图片描述

3.3.斐波那契数列法

斐波那契数列法:
原理: 以斐波那契数列性质 f(n + 1) = f(n) + f(n - 1)为转移方程。
从计算效率、空间复杂度上看,斐波那契数列法是本题的最佳解法。

int fbnq(int n)
{int con = (int)1e9 + 7;int first = 0;int second = 1;int tem = 0;while (n--){tem = first + second;first = second % con;second = tem % con;}return first;
}
int ClimbStairs(int n) {return fbnq(n + 1);
}
int main() {int n;printf("请输入楼梯的阶数:");scanf("%d", &n);int ways = ClimbStairs(n);printf("%d 阶楼梯一共有 %d 种跳法。\n", n, ways);return 0;
}

在这里插入图片描述

四.注意细节

为什么要模1000000007。
参考:https://link.zhihu.com/?target=https%3A//www.liuchuo.net/archives/645
大数相乘,大数的排列组合等为什么要取模
一、1000000007是一个质数(素数),对质数取余能最大程度避免结果冲突/重复
二、int32位的最大值为2147483647,所以对于int32位来说1000000007足够大。int64位的最大值为2^63-1,用最大值模1000000007的结果求平方,不会在int64中溢出。
所以在大数相乘问题中,因为(a∗b)%c=((a%c)∗(b%c))%c,所以相乘时两边都对1000000007取模,再保存在int64里面不会溢出。
这道题为什么要取模,取模前后的值不就变了吗?
确实:取模前 f(43) = 701408733, f(44) = 1134903170, f(45) = 1836311903, 但是 f(46) > 2147483647结果就溢出了。
取模后 f(43) = 701408733, f(44) = 134903163 , f(45) = 836311896, f(46) = 971215059没有溢出。取模之后能够计算更多的情况,如 f(46)。这道题的测试答案与取模后的结果一致。

总结一下,这道题要模1000000007的根本原因是标准答案取模了1000000007。不过大数情况下为了防止溢出,模1000000007是通用做法,原因见第一点。

相关文章:

【青蛙跳台阶问题 —— (三种算法)】

青蛙跳台阶问题 —— (三种算法&#xff09; 一.题目介绍1.1.题目1.2.图示 二.解题思路三.题解及其相关算法3.1.递归分治法3.2.动态规划算法&#xff08;Dynamic Programming&#xff09;3.3.斐波那契数列法 四.注意细节 一.题目介绍 1.1.题目 一只青蛙一次可以跳上1级台阶&am…...

联想yoga AMD处理器 转接头无法电量外接显示器

第一次买AMD的处理器&#xff0c;当时就是为了yogaAMD这款的接口要比英特尔的接口多&#xff0c;没想到AMD处理器真的问题多。经常蓝屏不说&#xff0c;偶尔还点不亮外接显示器。遇到这种问题&#xff0c;不是什么驱动问题&#xff0c;可能你按照网上各种方法打开设备管理器→显…...

OSG粒子系统与阴影 - ​​​​​​​阴影shadow(7)

OSG阴影 在虚拟现实仿真中&#xff0c;为了真实地模拟自然效果&#xff0c;阴影效果是不可缺少的&#xff0c;它对一个场景的真实性是非常重要的。在游戏或仿真中&#xff0c;一个高效的阴影往往能够提供非常强悍的视觉真实感。 osgShadow库 在OSG中专门定义了一个名字空间osg…...

vue3项目中使用富文本编辑器

前言 适配 Vue3 的富文本插件不多&#xff0c;我看了很多插件官网&#xff0c;也有很多写的非常棒的&#xff0c;有UI非常优雅让人耳目一新的&#xff0c;也有功能非常全面的。 如&#xff1a; Quill&#xff0c;简单易用&#xff0c;功能全面。editorjs&#xff0c;UI极其优…...

Java EE 进程线程

JavaEE 进程&线程 文章目录 JavaEE 进程&线程1. 进程1.1 概念1.2 进程管理1.3 PCB (Process Control Block) 2. 线程2.1 概念2.1 线程与进程的区别2.3 创建线程 1. 进程 1.1 概念 什么是进程&#xff1f; 进程是操作系统对一个正在执行的程序的一种抽象 我们可以打开…...

GPT写SQL的模版

表&#xff1a;profit_loss_sum_m_snapshot 计算字段&#xff1a;成本cost_whole求和&#xff0c;收入income_whole求和&#xff0c;收入求和-成本求和&#xff0c;成本目标cost_target求和&#xff0c;收入求和-成本目标求和 条件&#xff1a;日期statis_date在2023-11-01&…...

蓝桥杯官网练习题(平均)

问题描述 有一个长度为 n 的数组&#xff08; n 是 10 的倍数&#xff09;&#xff0c;每个数 ai 都是区间 [0,9] 中的整数。小明发现数组里每种数出现的次数不太平均&#xff0c;而更改第 i 个数的代价为 bi&#xff0c;他想更改若干个数的值使得这 10 种数出现的次数相等…...

【无标题】动手学深度学习_现代神经网络_未完

这里写目录标题 深度学习之前的网络 AlexNetAlexNet得到了竞赛冠军AlexNet架构Alex net更多细节数据增强 VGGNiN知识补充flop暂退法 drop_out 深度学习之前的网络 1、核方法 机器学习 SVM现在还是很广泛的使用&#xff0c;因为对调参的需求不那么大&#xff0c;对调参不太敏感…...

Java王者荣耀

GameFrame 图片 package 王者荣耀;import java.awt.*; import java.awt.event.ActionEvent; import java.awt.event.ActionListener; import java.awt.event.KeyAdapter; import java.awt.event.KeyEvent; import java.io.File; import java.util.ArrayList;import javax.soun…...

【理解ARM架构】操作寄存器实现UART | 段的概念 | IDE背后的命令

&#x1f431;作者&#xff1a;一只大喵咪1201 &#x1f431;专栏&#xff1a;《理解ARM架构》 &#x1f525;格言&#xff1a;你只管努力&#xff0c;剩下的交给时间&#xff01; 目录 &#x1f360;操作寄存器实现UART&#x1f35f;UART原理&#x1f35f;编程 &#x1f360;…...

python 左值查找 右值查找

左值查找 在一组数据中查找出 数字x 在这组数据中第一次出现的索引并输出&#xff0c;没有找到则输出-1查找方式&#xff1a;二分查找 数据前提&#xff1a;一组数据要有序一组数据&#xff1a; arr [2, 3, 3, 3, 5, 7, 9, 11, 13, 15, 17]测试&#xff1a; 示例1&#xff…...

机器学习之自监督学习(四)MoCo系列翻译与总结(二)

MoCo中相关工作的对比分析 去噪自动编码器&#xff08;Denoising Autoencoder&#xff09;是一种用于学习数据表示的神经网络模型。它的主要目标是通过去除输入数据中的噪声&#xff0c;学习到输入数据的有用表示&#xff0c;从而提高模型对干净数据的鲁棒性。下面是对去噪自动…...

元宇宙企业3d数字展厅轻松低本搭建更全面、多元、趣味化的展览

对所有企业来说&#xff0c;拥有一个3D线上展厅是互联网营销必不可少的部分&#xff0c;但是3D线上展厅定制周期长费用高&#xff0c;让很多企业公司望而却步&#xff0c;web3d开发公司制作的3D线上企业展厅制作平台备导览地图、语音解说、交互热点、全景漫游、自主行走、链接跳…...

华为OD机试真题-开源项目热榜-2023年OD统一考试(C卷)

题目描述: 某个开源社区希望将最近热度比较高的开源项目出一个榜单,推荐给社区里面的开发者。对于每个开源项目,开发者可以进行关注(watch)、收藏(star)、fork、提issue、提交合并请求(MR)等。 数据库里面统计了每个开源项目关注、收藏、fork、issue、MR的数量,开源项目的热…...

深入探索Maven:优雅构建Java项目的新方式(一)

Maven高级 1&#xff0c;分模块开发1.1 分模块开发设计1.2 分模块开发实现 2&#xff0c;依赖管理2.1 依赖传递与冲突问题2.2 可选依赖和排除依赖方案一:可选依赖方案二:排除依赖 3&#xff0c;聚合和继承3.1 聚合步骤1:创建一个空的maven项目步骤2:将项目的打包方式改为pom步骤…...

Shopee如何入驻?如何防封?

Shopee作为东南亚领航电商平台&#xff0c;面向东南亚蓝海市场&#xff0c;近年来随着东南亚市场蒸蒸日上&#xff0c;虾皮也吸引了大批量的跨境商家入驻。那么接下来就给想要入驻的虾皮小白一个详细的安全入驻教程。 一、商家如何入驻 虾皮与LAZADA最大的区别就是商家即卖家&…...

2024年第十六届山东省职业院校技能大赛中职组 “网络安全”赛项竞赛正式卷任务书

2024年第十六届山东省职业院校技能大赛中职组 “网络安全”赛项竞赛正式卷任务书 2024年第十六届山东省职业院校技能大赛中职组 “网络安全”赛项竞赛正式卷A模块基础设施设置/安全加固&#xff08;200分&#xff09;A-1&#xff1a;登录安全加固&#xff08;Windows, Linux&am…...

Python编程基础

Python是一种简单易学的编程语言&#xff0c;广泛应用于Web开发、数据分析、人工智能等领域。无论您是初学者还是有一定编程经验的人士&#xff0c;都可以从Python的基础知识开始建立自己的编程技能。 目录 理论Python语言的发展程序设计语言的分类静态语言与脚本语言的区别 代…...

python类和对象

1.使用对象组织数据 class Student:nameNone #记录名字 stu1Student() #创建对象 stu1.name"abc" #为对象属性赋值2.类的定义和使用 2.1成员方法的定义语法 传参的时候self是透明的&#xff0c;不用管 class Stu:nameNonedef sayHi(self):print(f"你好&#x…...

ubuntu操作系统中docker下Hadoop分布式前置环境配置实验

版本&#xff1a; centos7 hadoop 3.1.3 java JDK:1.8 集群规划&#xff1a; masterslave1slave2HDFS NameNode DataNode DataNode SecondryNameNode DataNode YARNNodeManager ResourceManage NodeManager NodeManager 1.docker容器&#xff1a; 把普通用户加入到docker组&am…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

srs linux

下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

基于Java+MySQL实现(GUI)客户管理系统

客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息&#xff0c;对客户进行统一管理&#xff0c;可以把所有客户信息录入系统&#xff0c;进行维护和统计功能。可通过文件的方式保存相关录入数据&#xff0c;对…...

搭建DNS域名解析服务器(正向解析资源文件)

正向解析资源文件 1&#xff09;准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2&#xff09;服务端安装软件&#xff1a;bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...

c# 局部函数 定义、功能与示例

C# 局部函数&#xff1a;定义、功能与示例 1. 定义与功能 局部函数&#xff08;Local Function&#xff09;是嵌套在另一个方法内部的私有方法&#xff0c;仅在包含它的方法内可见。 • 作用&#xff1a;封装仅用于当前方法的逻辑&#xff0c;避免污染类作用域&#xff0c;提升…...