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

数楼梯(加强版)

数楼梯(加强版)

题目背景:

  小明一天放学回家,看到从1楼到2楼共有n个台阶,因为好奇,他想尝试一下总共有几种方案到二楼?他可以1步,2步,3步的跳,不能跳3步以上.
  他试了很多次都没有解决这个问题,于是请求聪明的你帮忙解决这个问题.

题目描述:

1楼到2楼楼梯有n级台阶。小明每次可以爬一格、走两格或者跨三格。问最终有几种方案到二楼?答案对998244353取模。

输入格式:

一行一个数n。

输出格式:

一行一个数,表示方案数。

输入输出样例

输入 #1:

3

输出 #1:

4

输入 #2:

5

输出 #2:

13

提示说明:

 n≤1000  
 时间:1000ms   
 空间:256M  
 (上楼梯时不能往回走)
 如果觉得这道题太难可以前往P1255先做数楼梯简单版:
 https://www.luogu.com.cn/problem/P1255

思路:

  1.暴力法

  很容易看出来,这是一道递归题,我们可以用暴力递归来解决。

#include<iostream> 
using namespace std; 
static const int mod=998244353;
long long sum=0;
int n;
long long fun(int x){if(x==n)return 1;if(x>n)return 0;long long s1=0,s2=0,s3=0;s1+=fun(x+1)%mod;s2+=fun(x+2)%mod;s3+=fun(x+3)%mod;return (s1+s2+s3)%mod;
}
int main(){cin>>n;cout<<fun(0)<<endl;		return 0;
}

但是这个份代码会超时,非常慢,所以要进行优化!

2.递推法

我们用 f(x) 表示爬到第 x 级台阶的方案数,考虑最后一步可能跨了一级台阶,也可能跨了两级台阶,所以我们可以列出如下式子:
f(x)=f(x−1)+f(x−2)
它意味着爬到第 x 级台阶的方案数是爬到第 x−1 级台阶的方案数和爬到第 x−2 级台阶的方案数的和。很好理解,因为每次只能爬 1 级或 2 级,所以 f(x) 只能从 f(x−1)和 f(x−2) 转移过来,而这里要统计方案总数,我们就需要对这两项的贡献求和。

  以上是动态规划的转移方程,下面我们来讨论边界条件。我们是从第 0 级开始爬的,所以从第 0 级爬到第 0 级我们可以看作只有一种方案,即 f(0)=1;从第 0 级到第 1 级也只有一种方案,即爬一级,f(1)=1。这两个作为边界条件就可以继续向后推导出第 n 级的正确结果。我们不妨写几项来验证一下,根据转移方程得到 f(2)=2,f(3)=3,f(4)=5,……,我们把这些情况都枚举出来,发现计算的结果是正确的。

  我们不难通过转移方程和边界条件给出一个时间复杂度和空间复杂度都是 O(n)的实现,但是由于这里的 f(x) 只和 f(x−1)) 与 f(x−2)有关,所以我们可以用「滚动数组思想」把空间复杂度优化成 O(1)。下面的代码中给出的就是这种实现。

#include<iostream> 
using namespace std; 
static const int mod=998244353;
void fun(int n){long long max[1001];int i=0;max[0]=1;max[1]=2;max[2]=4;for(int j=3;j<n;j++)max[j]=(max[j-1]+max[j-2]+max[j-3])%mod;cout<<max[n-1]<<endl;
}
int main(){int n;cin>>n;fun(n);		return 0;
}

总结:

  对于这道题,有些像斐波那契数列,需要将递归进行优化才可以解决。

题目链接:

数楼梯(加强版) - 洛谷https://www.luogu.com.cn/problem/U267577

相关文章:

数楼梯(加强版)

数楼梯(加强版) 题目背景: 小明一天放学回家,看到从1楼到2楼共有n个台阶,因为好奇,他想尝试一下总共有几种方案到二楼?他可以1步,2步,3步的跳,不能跳3步以上. 他试了很多次都没有解决这个问题,于是请求聪明的你帮忙解决这个问题. 题目描述: 1楼到2楼楼梯有n级台阶。小明每…...

MySQL-数据类型

数据类型简介数据表由多列字段构成&#xff0c;每一个字段指定了不同的数据类型&#xff0c;指定了数据类型之后&#xff0c;也就决定了向字段插入的数据内容。不同的数据类型也决定了 MySQL 在存储它们的时候使用的方式&#xff0c;以及在使用它们的时候选择什么运算符号进行运…...

剑指 Offer 32 - II. 从上到下打印二叉树 II(java解题)

剑指 Offer 32 - II. 从上到下打印二叉树 II&#xff08;java解题&#xff09;1. 题目2. 解题思路3. 数据类型功能函数总结4. java代码5. 踩坑记录1. 题目 从上到下按层打印二叉树&#xff0c;同一层的节点按从左到右的顺序打印&#xff0c;每一层打印到一行。 例如: 给定二叉…...

C#网络爬虫开发

1前言爬虫一般都是用Python来写&#xff0c;生态丰富&#xff0c;动态语言开发速度快&#xff0c;调试也很方便但是我要说但是&#xff0c;动态语言也有其局限性&#xff0c;笔者作为老爬虫带师&#xff0c;几乎各种语言都搞过&#xff0c;现在这个任务并不复杂&#xff0c;用我…...

Fastjson 总结

0x00 前言 这一篇主要是针对已经完成的fastjson系列做一个知识点总结&#xff0c;一来是为了更加有条理的梳理已经存在的内容&#xff0c;二来是为了更好的复习和利用。 0x01 Fastjson基础知识点 1.常见问题&#xff1a; 问&#xff1a;fastjson的触发点是什么&#xff1f;…...

文件路径模块os.path

文件路径模块os.path 文章目录文件路径模块os.path1.概述2.解析路径2.1.拆分路径和文件名split2.2.获取文件名称basename2.3.返回路径第一部分dirname2.4.扩展名称解析路径splitext2.5.返回公共前缀路径commonprefix3.创建路径3.1.拼接路径join3.2.获取家目录3.3.规范化路径nor…...

Kerberos简单介绍及使用

Kerberos作用 简单来说安全相关一般涉及以下方面&#xff1a;用户认证&#xff08;Kerberos的作用&#xff09;、用户授权、用户管理.。而Kerberos功能是用户认证&#xff0c;通俗来说解决了证明A是A 的问题。 认证过程&#xff08;时序图&#xff09; 核心角色/概念 KDC&…...

DOM编程-全选、全不选和反选

<!DOCTYPE html> <html> <head> <meta charset"utf-8"> <title>全选、全不选和反选</title> </head> <body bgcolor"antiquewhite"> <script type"text/jav…...

C++11可变模板参数

C11可变模板参数一、简介二、语法三、可变模版参数函数3.1、递归函数方式展开参数包3.2、逗号表达式展开参数包一、简介 C11的新特性–可变模版参数&#xff08;variadic templates&#xff09;是C11新增的最强大的特性之一&#xff0c;它对参数进行了高度泛化&#xff0c;它能…...

Linux多线程

目录 一、认识线程 1.1 线程概念 1.2 页表 1.3 线程的优缺点 1.3.1 优点 1.3.2 缺点 1.4 线程异常 二、进程 VS 线程 三、Linux线程控制 3.1 POSIX线程库 3.1 线程创建 3.3 线程等待 3.4 线程终止 3.4.1 return退出 3.4.2 pthread_exit() 3.4.3 pthread_cancel…...

Webpack5 环境下 Openlayers 标注(Icon) require 引入图片问题

Webpack5 环境下 Openlayers 标注&#xff08;Icon&#xff09; require 引入图片问题环境版本Openlayers 使用 require 问题Webpack5 正确配置构建新环境的时候&#xff0c;偶然发现 Openlayers 使用 require 的方式加载图片&#xff08;Icon&#xff09;报错&#xff0c;开始…...

Zookeeper安装部署

文章目录Zookeeper安装部署Zookeeper安装部署 将Zookeeper安装包解压缩&#xff0c; [rootlocalhost opt]# ll 总用量 14032 -rw-r--r--. 1 root root 12392394 10月 13 11:44 apache-zookeeper-3.6.0-bin.tar.gz drwxrwxr-x. 6 root root 4096 10月 18 01:44 redis-5.0.4 …...

Cow Acrobats ( 临项交换贪心 )

题目大意&#xff1a; N 头牛 &#xff0c; 每头牛有一个重量(Weight)和一个力量(Strenth) &#xff0c; N头牛进行排列 &#xff0c; 第 i 头牛的风险值为其上所有牛总重减去自身力量 &#xff0c; 问如何排列可以使最大风险值最小 &#xff0c; 求出这个最小的最大风险值&am…...

MySQL:为什么说应该优先选择普通索引,尽量避免使用唯一索引

前言 在使用MySQL的过程中&#xff0c;随着表数据的逐渐增多&#xff0c;为了更快的查询我们需要的数据&#xff0c;我们会在表中建立不同类型的索引。 今天我们来聊一聊&#xff0c;普通索引和唯一索引的使用场景&#xff0c; 以及为什么说推荐大家优先使用普通索引&#xf…...

Spring Cloud alibaba之Feign

JAVA项目中如何实现接口调用&#xff1f;HttpclientHttpclient是Apache Jakarta Common下的子项目&#xff0c;用来提供高效的、最新的、功能丰富的支持Http协议的客户端编程工具包&#xff0c;并且它支持HTTP协议最新版本和建议。HttpClient相比传统JDK自带的URL Connection&a…...

零信任-Google谷歌零信任介绍(3)

谷歌零信任的介绍&#xff1f; "Zero Trust" 是一种网络安全模型&#xff0c;旨在通过降低网络中的信任级别来防止安全威胁。在零信任模型中&#xff0c;不论请求来自内部网络还是外部网络&#xff0c;系统都将对所有请求进行详细的验证和审核。这意味着每次请求都需…...

Numpy基础——人工智能基础

文章目录一、Numpy概述1.优势2.numpy历史3.Numpy的核心&#xff1a;多维数组4.numpy基础4.1 ndarray数组4.2 内存中的ndarray对象一、Numpy概述 1.优势 Numpy(Nummerical Python),补充了Python语言所欠缺的数值计算能力&#xff1b;Numpy是其它数据分析及机器学习库的底层库&…...

电商仓储与配送云仓是什么?

仓库是整个供给链的关键局部。它们是产品暂停和触摸的点&#xff0c;耗费空间和时间(工时)。空间和时间反过来也是费用。经过开发数学和计算机模型来微调仓库的规划和操作&#xff0c;经理能够显著降低与产品分销相关的劳动力本钱&#xff0c;进步仓库空间应用率&#xff0c;并…...

【零基础入门前端系列】—HTML介绍(一)

【零基础入门前端系列】—HTML介绍&#xff08;一&#xff09; 一、什么是HTML HTML是用来描述网页的一种语言HTML指的是超文本标记语言&#xff1a;HyperText Markup LanguageHTML不是一种编程语言&#xff0c;而是一种超文本标记语言&#xff0c;标记语言是一套标记标签(ma…...

Elasticsearch索引库和文档的相关操作

前言&#xff1a;最近一直在复习Elasticsearch相关的知识&#xff0c;公司搜索相关的技术用到了这个&#xff0c;用公司电脑配了环境&#xff0c;借鉴网上的课程进行了总结。希望能够加深自己的印象以及帮助到其他的小伙伴儿们&#x1f609;&#x1f609;。 如果文章有什么需要…...

使用Python,Opencv检测图像,视频中的猫

使用Python&#xff0c;Opencv检测图像&#xff0c;视频中的猫&#x1f431; 这篇博客将介绍如何使用Python&#xff0c;OpenCV库附带的默认Haar级联检测器来检测图像中的猫。同样的技术也可以应用于视频流。这些哈尔级联由约瑟夫豪斯&#xff08;Joseph Howse&#xff09;训练…...

浅谈域名和服务器集约化管理的误区

一个正常的网站通常由域名、网站程序、服务器三个部分组成&#xff0c;网站程序由单位开发设计&#xff0c;而域名和服务器则需要租用购买&#xff0c;那么域名和服务器之间的关系是什么&#xff1f;如何实现域名和服务器的有效管理呢&#xff1f; 服务器和域名的关系 服务器…...

迪赛智慧数——柱状图(正负条形图):20212022人才求职最关注的因素

效果图从近两年职场跳槽方向看&#xff0c;相比此前人们对高薪大厂趋之若鹜&#xff0c;如今职场人更关注业务前景。根据相关数据显示&#xff0c;职场人求职最关注的因素中&#xff0c;“薪资福利”权重下降&#xff0c;“个人发展”权重上升&#xff0c;“业务前景”首次进入…...

网络安全-黑帽白帽红客与网络安全法

网络安全-黑帽白帽红客与网络安全法 本章内容较少&#xff0c;因为刚开端。 黑客来源于hacker 指的是信息安全里面&#xff0c;能够自由出入对方系统&#xff0c;指的是擅长IT技术的电脑高手 黑帽黑客-坏蛋&#xff0c;研究木马的&#xff0c;找漏洞的&#xff0c;攻击网络或者…...

Xpath元素定位之同级节点,父节点,子节点

XPath学习:轴(8)——following-siblingXPath 是一门在 XML 文档中查找信息的语言。XPath 可用来在 XML 文档中对元素和属性进行遍历。XPath 是 W3C XSLT 标准的主要元素&#xff0c;并且 XQuery 和 XPointer 同时被构建于 XPath 表达之上。推荐一个挺不错的网站&#xff1a;htt…...

华为OD机试 - 挑选字符串(Python)| 真题+思路+代码

挑选字符串 题目 给定 a-z,26 个英文字母小写字符串组成的字符串 A 和 B, 其中 A 可能存在重复字母,B 不会存在重复字母, 现从字符串 A 中按规则挑选一些字母可以组成字符串 B 挑选规则如下: 同一个位置的字母只能挑选一次, 被挑选字母的相对先后顺序不能被改变, 求最…...

python笔记-- “__del__”析构方法

-#### 1、基本概念&#xff08;构造函数与析构函数&#xff09; 特殊函数&#xff1a;由系统自动执行&#xff0c;在程序中不可显式地调用他们 构造函数&#xff1a; 建立对象时对对象的数据成员进行初始化&#xff08;对象初始化&#xff09; 析构函数&#xff1a; 对象生命期…...

支付系统核心架构设计思路(万能通用)

文章目录1. 支付系统总览核心系统交互业务图谱2. 核心系统解析交易核心交易核心基础交易类型抽象多表聚合 & 订单关联支付核心支付核心总览支付行为编排异常处理渠道网关资金核算3. 服务治理平台统一上下文数据一致性治理CAS校验幂等 & 异常补偿对账准实时对账DB拆分异…...

python实现mongdb的双活

如何用python实现mongdb的双活&#xff0c;两个数据库实时同步&#xff1f; 可以使用Pymongo库&#xff0c;它可以提供同步的API来实现MongoDB的双活&#xff0c;两个数据库实时同步。还可以使用MongoDB的复制集功能来进行实时同步。 Pymongo库提供什么同步的API来实现MongoD…...

LeetCode-110. 平衡二叉树

目录题目分析递归法题外话题目来源 110. 平衡二叉树 题目分析 平很二叉树:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。 二叉树节点的深度和二叉树节点的高度 递归法 递归三步曲 1.明确递归函数的参数和返回值 参数&#xff1a;当前传入节点。 返回值…...

石家庄商城网站建设/湖北疫情最新消息

金木水火土命查询表五行相生的顺序是:水生木,木生火,火生土,土生金,金生水; 五行相克的顺序是:金克木,木克土,土克水,水克火,火克金.金木水火土命查询表(2009-03-30)土命 金命 水命 查询表 金木 甲子年生海中金命&#xff08;1924&#xff0c;1984&#xff09; 乙丑年生海中金…...

设计师网站图片/如何营销推广

DHCP 协议简介DHCP是Dynamic Host Configuration Protocol的缩写&#xff0c;它的前身是BOOTP。DHCP可以说是BOOTP的增强版本&#xff0c;是基于C/S模式的&#xff0c;它提供了一种动态指定IP地址和配置参数的机制。服务器端监听UDP 67端口&#xff0c;客户端使用UDP 68端口DHC…...

怎么知道网站的域名/微信营销推广

一&#xff0c;Mllib的数据格式 1&#xff0c;本地向量 本地向量是存储在本地节点上的&#xff0c;其基本数据类型是Vector&#xff0c;其有两个子集&#xff0c;分别是密集的与稀疏的&#xff0c;我们一般使用Vectors工厂类来实现。如&#xff1a; Vectors.dese(1.0,2.0,3.…...

拉萨营销型网站建设/怎么用手机创建网站

本文章给大家介绍在php中类和对象的protected与const属性用法&#xff0c;有需要了解的朋友可参考参考。const属性用const属性定义的字段是一个常量&#xff0c;类中的常量和静态变量类似&#xff0c;不同之处就是常量的值一旦赋值不能被改变。const定义常量不需要加$符号&…...

做企业官网需要多少钱/seo营销技巧培训班

小练习&#xff0c;小练习哈&#xff0c;直接上代码&#xff0c;上课上的太无聊了&#xff0c;来玩一玩vue来了~ <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"…...

怎么打帮人做网站开发的广告/北京口碑最好的教育机构

1.列举你在工作中常用的几个git命令&#xff1f; 新增文件的命令&#xff1a;git add file或者git add . 提交文件的命令&#xff1a;git commit –m或者git commit –a 查看工作区状况&#xff1a;git status –s 拉取合并远程分支的操作&#xff1a;git fetch/git merge或…...