(动态规划) 剑指 Offer 10- II. 青蛙跳台阶问题 ——【Leetcode每日一题】
❓剑指 Offer 10- II. 青蛙跳台阶问题
难度:简单
一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。
示例 1:
输入:n = 2
输出:2
示例 2:
输入:n = 7
输出:21
示例 3:
输入:n = 0
输出:1
提示:
0 <= n <= 100
注意:本题与 70. 爬楼梯 相同。
💡思路:动态规划
当 n = 1 时,只有一种跳法:

当 n = 2 时,有两种跳法:

跳 n 阶台阶,可以先跳 1 阶台阶,再跳 n-1 阶台阶;或者先跳 2 阶台阶,再跳 n-2 阶台阶。而 n-1 和 n-2 阶台阶的跳法可以看成子问题,该问题的递推公式为:
f ( n ) = { 1 n = 0 1 n = 1 2 n = 2 f ( n − 1 ) + f ( n − 2 ) n > 1 f(n)=\left\{\begin{array}{rcc}1&\quad n=0\\1&\quad n=1\\2&\quad n=2\\f(n-1)+f(n-2)&\quad n>1\end{array}\right. f(n)=⎩ ⎨ ⎧112f(n−1)+f(n−2)n=0n=1n=2n>1
🍁代码:(C++、Java)
C++
class Solution {
public:int numWays(int n) {int ans = 1;int pre1 = 1, pre2 = 1;for(int i = 2; i <= n; i++){ans = (pre1 + pre2) % 1000000007;pre1 = pre2;pre2 = ans;}return ans;}
};
Java
class Solution {public int numWays(int n) {int ans = 1;int pre1 = 1, pre2 = 1;for(int i = 2; i <= n; i++){ans = (pre1 + pre2) % 1000000007;pre1 = pre2;pre2 = ans;}return ans;}
}
🚀 运行结果:

🕔 复杂度分析:
- 时间复杂度: O ( n ) O(n) O(n),循环执行
n次,每次花费常数的时间代价,故渐进时间复杂度为 O ( n ) O(n) O(n)。 - 空间复杂度: O ( 1 ) O(1) O(1),只用了常数个变量作为辅助空间。
题目来源:力扣。
放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!
注: 如有不足,欢迎指正!
相关文章:
(动态规划) 剑指 Offer 10- II. 青蛙跳台阶问题 ——【Leetcode每日一题】
❓剑指 Offer 10- II. 青蛙跳台阶问题 难度:简单 一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。 答案需要取模 1e97(1000000007),如计算初始结果为:1…...
物联网WIFI 模块AT指令版本七大元凶
前言 目前我们讨论的这个问题,并不是说WIFI方案不具备以应的功能。而是指在同一个AT固件下可能存在的问题。由于各厂商AT指令的开发深度不同,导致各厂商之间的AT指令差异很大。我总结了一些问题,可能是导致目前AT指令不好用元凶。 底层库问题…...
Qt 正则(数据格式校验、替换指定格式数据、获取匹配数据)
头文件引用 #include <QRegExp>初始化QRegExp实列 QRegExp re("^\\d{1,3},\\d{1,3}$");数据格式验证 QRegExp re("^\\d{1,3},\\d{1,3}$"); QString msg "12,33"; if(re.exactMatch()){// 验证通过 }else{//验证不通过 }替换数…...
网络层协议——ip
文章目录 1. 网络层2. IP协议2.1 协议头格式 3. 网段划分3.1 特殊的IP地址3.2 IP地址的数量限制 4. 私有IP地址和公网IP地址 1. 网络层 在应用层解决了如何读取完整报文、序列化反序列化、协议处理问题。在传输层解决了可靠性问题。那么网络层IP的作用是在复杂的网络环境中确定…...
Qt6和Rust结合构建桌面应用
桌面应用程序是原生的、快速的、安全的,并提供Web应用程序无法比拟的体验。 Rust 是一种低级静态类型多范式编程语言,专注于安全性和性能,解决了 C/C 长期以来一直在努力解决的问题,例如内存错误和构建并发程序。 在桌面应用程序开…...
Kubernetes(K8S)简介
Kubernetes (K8S) 是什么 它是一个为 容器化 应用提供集群部署和管理的开源工具,由 Google 开发。Kubernetes 这个名字源于希腊语,意为“舵手”或“飞行员”。k8s 这个缩写是因为 k 和 s 之间有八个字符的关系。 Google 在 2014 年开源了 Kubernetes 项…...
面试中问:React中函数组件和class组件的区别,hooks模拟生命周期
React中函数组件和class组件的区别,hooks模拟生命周期 React中函数组件和class组件的区别hooks模拟生命周期 React中函数组件和class组件的区别 函数组件: 定义:函数组件是使用纯函数定义的组件,它接受 props 作为参数并返回 JSX。简洁性&am…...
Python高光谱遥感数据处理与高光谱遥感机器学习方法应用
本文提供一套基于Python编程工具的高光谱数据处理方法和应用案例。 本文涵盖高光谱遥感的基础、方法和实践。基础篇以学员为中心,用通俗易懂的语言解释高光谱的基本概念和理论,旨在帮助学员深入理解科学原理。方法篇结合Python编程工具,专注…...
Java实现接收xml格式数据并解析,返回xml格式数据
需求描述:后端接受xml格式数据,解析出相应数据,并返回xml格式数据。 <!--XML解析--><dependency><groupId>com.fasterxml.jackson.dataformat</groupId><artifactId>jackson-dataformat-xml</artifactId>…...
【C++】初步认识模板
🏖️作者:malloc不出对象 ⛺专栏:C的学习之路 👦个人简介:一名双非本科院校大二在读的科班编程菜鸟,努力编程只为赶上各位大佬的步伐🙈🙈 目录 前言一、泛型编程二、函数模板2.1 函…...
Ansible 临时命令搭建安装仓库
创建一个名为/ansible/yum.sh 的 shell 脚本,该脚本将使用 Ansible 临时命令在各个受管节点上安装 yum 存储库. 存储库1: 存储库的名称为 EX294_BASE 描述为 EX294 base software 基础 URL 为 http://content/rhel8.0/x86_64/dvd/BaseOS GPG 签名检查为…...
phpstorm动态调试
首先在phpstudy搭建好网站,在管理拓展开启xdebug拓展 查看php.ini配置已经更改 需要增添修改一下设置 [Xdebug] zend_extensionD:/phpstudy_pro/Extensions/php/php5.6.9nts/ext/php_xdebug.dll xdebug.collect_params1 xdebug.collect_return1 xdebug.auto_trace…...
二叉树的层序遍历及完全二叉树的判断
文章目录 1.二叉树层序遍历 2.完全二叉树的判断 文章内容 1.二叉树层序遍历 二叉树的层序遍历需要一个队列来帮助实现。 我们在队列中存储的是节点的地址,所以我们要对队列结构体的数据域重定义, 以上代码 从逻辑上来讲就是1入队,1出队&am…...
java八股文面试[JVM]——JVM内存结构
参考: JVM学习笔记(一)_卷心菜不卷Iris的博客-CSDN博客 JVM是运行在操作系统之上的,它与硬件没有直接的交互 JVM内存结构: 方法区:存储已被虚拟机加载的类元数据信息(元空间) 堆:存放对象实…...
Kafka基本使用
查看Kafka的进程是否在运行 #命令行终端中运行如下命令 ps -ef | grep kafkafind / -iname kafka-server-start.shcd /usr/local/kafka/bin/#启动kafka ./kafka-server-start.sh -daemon /usr/local/kafka/config/server.propertiesKafka默认使用9092端口提供服务…...
【目标检测】理论篇(2)YOLOv3网络构架及其代码实现
网络构架图: 代码实现: import math from collections import OrderedDictimport torch.nn as nn#---------------------------------------------------------------------# # 残差结构 # 利用一个1x1卷积下降通道数,然后利用一个3x3卷…...
k8s之工作负载、Deployment、DaemonSet、StatefulSet、Job、CronJob及GC
文章目录 1、工作负载1.1、定义1.2、分类 2、Deployment2.1、定义2.2、Deployment创建2.3、Deployment 更新机制2.3.1、比例缩放(Proportional Scaling)2.3.2、HPA(动态扩缩容)2.3.2.1、需要先安装metrics-server2.3.2.2、配置hpa…...
IDEA项目实践——Element UI概述
系列文章目录 IDEA项目实践——JavaWeb简介以及Servlet编程实战 IDEA项目实践——Spring当中的切面AOP IDEA项目实践——Spring框架简介,以及IOC注解 IDEA项目实践——动态SQL、关系映射、注解开发 IDEWA项目实践——mybatis的一些基本原理以及案例 文章目录 …...
Docker 容器学习笔记
Docker 容器学习笔记 容器的由来 早先,虚拟机通过操作系统实现相互隔离,保证应用程序在运行时相互独立,避免相互干扰。但是操作系统又笨又重,耗费资源严重: 容器技术只隔离应用程序的运行时环境但容器之间共享同一个…...
Day03-vue基础
Day03-vue基础 一 列表渲染 v-for这个指令可以实现列表渲染 1 数组 <ul><!-- v-for遍历的时候,key必须赋唯一值第一个参数是数组元素,第二个参数是元素下标--><li v-for="(item,index) in [1,3,5,7]" :key="item">{{item}}--{{index}…...
TDengine 快速体验(Docker 镜像方式)
简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能,本节首先介绍如何通过 Docker 快速体验 TDengine,然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker,请使用 安装包的方式快…...
椭圆曲线密码学(ECC)
一、ECC算法概述 椭圆曲线密码学(Elliptic Curve Cryptography)是基于椭圆曲线数学理论的公钥密码系统,由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA,ECC在相同安全强度下密钥更短(256位ECC ≈ 3072位RSA…...
【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)
🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...
微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...
【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)
骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术,它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton):由层级结构的骨头组成,类似于人体骨骼蒙皮 (Mesh Skinning):将模型网格顶点绑定到骨骼上,使骨骼移动…...
IT供电系统绝缘监测及故障定位解决方案
随着新能源的快速发展,光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域,IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选,但在长期运行中,例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...
【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)
本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...
AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别
【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而,传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案,能够实现大范围覆盖并远程采集数据。尽管具备这些优势…...
基于IDIG-GAN的小样本电机轴承故障诊断
目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) 梯度归一化(Gradient Normalization) (2) 判别器梯度间隙正则化(Discriminator Gradient Gap Regularization) (3) 自注意力机制(Self-Attention) 3. 完整损失函数 二…...
