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

【华为机试】2023年真题B卷(python)-猴子爬山

一、题目

题目描述:

一天一只顽猴想去从山脚爬到山顶,途中经过一个有个N个台阶的阶梯,但是这猴子有一个习惯:
每一次只能跳1步或跳3步,试问猴子通过这个阶梯有多少种不同的跳跃方式?

二、输入输出

输入描述:
输入只有一个整数N(0<N<=50)此阶梯有多少个台阶。
输出描述:
输出有多少种跳跃方式(解决方案数)。

三、示例

示例1:

输入输出示例仅供调试,后台判题数据一般不包含示例
输入:
50
输出:
122106097
示例2:

输入输出示例仅供调试,后台判题数据一般不包含示例
输入:
3
输出:
2

四、解题思路

这是一个经典的动态规划问题。我们可以使用动态规划的思想来解决这个问题。

首先,我们定义一个长度为N+1的数组dp,其中dp[i]表示通过i个台阶的跳跃方式的解决方案数。

然后,我们可以根据题目描述的规则,推导出状态转移方程:
dp[i] = dp[i-1] + dp[i-3]

解释一下这个状态转移方程的含义:

  • 当前位置i的解决方案数等于前一步位置i-1的解决方案数加上前一步位置i-3的解决方案数。
  • 这是因为,要到达当前位置i,可以从前一步位置i-1跳一步到达,也可以从前一步位置i-3跳三步到达。

接下来,我们可以使用动态规划的方法来计算解决方案数。我们从起始位置开始,逐步计算每个位置的解决方案数,直到达到目标位置N。

最后,返回目标位置N的解决方案数作为结果。

五、参考代码 

# -*- coding: utf-8 -*-
'''
@File    :   2023-B-猴子爬山.py
@Time    :   2023/12/29 19:30:20
@Author  :   mgc 
@Version :   1.0
@Desc    :   None
'''# import os
# import re
# import sys
# import copy
# import math
# import queue
# import functools
# from queue import Queue
# from collections import Counter, defaultdictdef count_jump_ways(N):if N <= 0:return 0# 定义动态规划数组dp = [0] * (N + 1)# 初始条件dp[0] = 1# 计算解决方案数for i in range(1, N + 1):dp[i] = dp[i - 1] + (dp[i - 3] if i >= 3 else 0)return dp[N]N = int(input())
result = count_jump_ways(N)
print(result)

相关文章:

【华为机试】2023年真题B卷(python)-猴子爬山

一、题目 题目描述&#xff1a; 一天一只顽猴想去从山脚爬到山顶&#xff0c;途中经过一个有个N个台阶的阶梯&#xff0c;但是这猴子有一个习惯&#xff1a; 每一次只能跳1步或跳3步&#xff0c;试问猴子通过这个阶梯有多少种不同的跳跃方式&#xff1f; 二、输入输出 输入描述…...

【Harmony OS - Stage应用模型】

基本概念 大类分为&#xff1a; Ability Module&#xff1a; 功能模块 、Library Module&#xff1a; 共享功能模块 编译时概念&#xff1a; Ability Module在编译时打包生成HAP&#xff08;Harmony Ability Package&#xff09;&#xff0c;一个应用可能会有多个HAP&#xf…...

Java 8 中的 Stream 轻松遍历树形结构!

可能平常会遇到一些需求&#xff0c;比如构建菜单&#xff0c;构建树形结构&#xff0c;数据库一般就使用父id来表示&#xff0c;为了降低数据库的查询压力&#xff0c;我们可以使用Java8中的Stream流一次性把数据查出来&#xff0c;然后通过流式处理&#xff0c;我们一起来看看…...

Openwrt修改Dropbear ssh root密码

使用ssh工具连接路由器 输入&#xff1a;passwd root 输入新密码 重复新密码 设置完成 rootImmortalWrt:~# passwd root Changing password for root New password:...

js 对象

js 对象定义 <!DOCTYPE html> <html> <body><h1>JavaScript 对象创建</h1><p id"demo1"></p> <p>new</p> <p id"demo"></p><script> // 创建对象&#xff1a; var persona {fi…...

【SpringBoot】常用注解

RequestBody&#xff1a;自动将请求体中的 json 数据转换为实体类对象。 这个例子凑巧传入的json属性键名和User键名一致&#xff0c;可以直接使用User实体类对象&#xff0c;如果键名不一致则需要用一个Map 类接收参数&#xff1a; PutMapping("/update")public R…...

【模拟电路】软件Circuit JS

一、模拟电路软件Circuit JS 二、Circuit JS软件配置 三、Circuit JS 软件 常见的快捷键 四、Circuit JS软件基础使用 五、Circuit JS软件使用讲解 欧姆定律电阻的串联和并联电容器的充放电过程电感器和实现理想超导的概念电容阻止电压的突变&#xff0c;电感阻止电流的突变LR…...

从入门到精通,30天带你学会C++【第十天:猜数游戏】

目录 Everyday English 前言 实战1——猜数游戏 综合指标 游玩方法 代码实现 最终代码 试玩时间 必胜策略 具体演示 结尾 Everyday English All good things come to those who wait. 时间不负有心人 前言 今天是2024年的第一天&#xff0c;新一年&#xff0c;新…...

使用ASP.NET MiniAPI 调试未匹配请求路径

本文将介绍如何在使用ASP.NET MiniAPI时调试未匹配到的请求路径。我们将详细讨论使用MapFallback方法、中间件等工具来解决此类问题。 1. 引言 ASP.NET MiniAPI是一个轻量级的Web API框架&#xff0c;它可以让我们快速地构建和部署RESTful服务。然而&#xff0c;在开发过程中如…...

数据结构: 位图

位图 概念 用一个bit为来标识数据在不在 功能 节省空间快速查找一个数在不在一个集合中排序 去重求两个集合的交集,并集操作系统中的磁盘标记 简单实现 1.设计思想:一个bit位标识一个数据, 使用char(8bit位)集合来模拟 2.预备工作:a.计算这个数在第几个char b.是这个ch…...

Nginx 反向代理负载均衡

Nginx 反向代理负载均衡 普通的负载均衡软件&#xff0c;如 LVS&#xff0c;其实现的功能只是对请求数据包的转发、传递&#xff0c;从负载均衡下的节点服务器来看&#xff0c;接收到的请求还是来自访问负载均衡器的客户端的真实用户&#xff1b;而反向代理就不一样了&#xf…...

SAP FIORI 初步了解

1、对网上存在的部分资料进行收集 一套适合 SAP UI5 开发人员循序渐进的学习教程 SAP Fiori 的学习路线指南 如何根据角色批量激活SAP Fiori服务 关于S/4和Fiori&#xff0c;你必须知道的10件事 SAP Fiori开发教程 SAP FIORI教程 面向ABAP开发人员&#xff0c;SAPUI5 Fiori开发…...

chrome浏览器记录不住网站登录状态,退出后再打开就需要重新登陆的解决办法

chrome浏览器记录不住网站登录状态&#xff0c;退出后再打开就需要重新登陆&#xff0c;比较繁琐。 解决办法&#xff1a; 1、chrome浏览器右上角三个竖的点&#xff0c;然后进入“设置”&#xff08;Settings&#xff09;&#xff0c;选择“隐私与安全”&#xff08;Privacy…...

Linux lpd命令教程:打印服务管理技巧全解析(附实例教程和注意事项)

Linux lpd命令介绍 lpd是Linux操作系统中的一个命令&#xff0c;全称为line printer daemon&#xff0c;其主要职责是管理和控制打印任务。lpd可以接收打印任务请求并将这些请求放入打印任务队列中。当打印机空闲时&#xff0c;lpd会自动将任务队列中的打印请求发送给打印机以…...

利用STM32和可控硅控制220V加热电路

利用STM32和可控硅控制220V加热电路 Chapter1 利用STM32和可控硅控制220V加热电路一、错误原理图二、正确原理图 Chapter2 可控硅驱动芯片MOC3081/3061Chapter3 一个MOC3061的可控硅触发电路的分析Chapter4 可控硅的两种触发方式&#xff1a;移相触发和过零触发1、过零触发2、移…...

在高并发场景下,缓存“雪崩”了怎么办

1. 缓存雪崩的常见原因 缓存“雪崩”是指&#xff0c;因为部分缓存节点不可用&#xff0c;而导致整个缓存系统&#xff08;甚至是整个服务系统&#xff09;不可用。缓存“雪崩”主要分为以下两种情况&#xff1a; 因缓存不支持 rehash 而导致的缓存“雪崩”缓存支持 rehash 时…...

本地git服务器的使用

Windows上使用&#xff1a; 首先要在windows开发机上生成密钥&#xff1a; 1.安装git&#xff0c;首先去git官网下载git&#xff0c;https://git-scm.com/downloads&#xff0c;下载.exe格式并安装。 2.从程序目录启动“Git Bash” 3.键入命令&#xff1a;ssh-keygen -t rsa -…...

Mybatis Java API - SqlSessionFactoryBuilder

在MyBatis中&#xff0c;用于与数据库进行交互的主要Java接口是SqlSession。通过这个接口&#xff0c;您可以执行命令、获取映射器并管理事务。稍后我们将更详细地讨论SqlSession本身&#xff0c;但首先我们必须学习如何获取SqlSession的实例。SqlSession是由SqlSessionFactory…...

【动态规划】 LCR 099. 最小路径和

LCR 099. 最小路径和 解题思路 采用动态规划的思路每次搜索都是向上或者向左进行搜索dp(grid, i, j) 的值取决于 dp(grid, i - 1, j) 和 dp(grid, i, j - 1) 返回的值。同时(i,j)到(i - 1,j - 1)有两种方法&#xff0c;所以一定存在重叠子问题设置备忘录Memo存储dp过程中所有…...

【51单片机系列】DS18B20温度传感器扩展实验之设计一个智能温控系统

本文是关于DS18B20温度传感器的一个扩展实验。 文章目录 一、相关元件介绍二、实验分析三、proteus原理图设计四、软件设计 本扩展实验实现的功能&#xff1a;利用DS18B20设计一个智能温度控制系统&#xff0c;具有温度上下限值设定。当温度高于上限值时&#xff0c;电机开启&a…...

2023年年度总结,一个小白的CSDN涨粉历程

前言 滚滚长江东逝水&#xff0c;一去不复返。 转眼间已到2024年节点&#xff0c;时间如滚滚长江水向东奔流不息&#xff0c;在长江消失之前&#xff0c;都不会停歇&#xff0c;也不会回头。人亦如此&#xff0c;不管是生活还是学习&#xff0c;都是不断往前走的过程&#xff…...

2023-12-17 LeetCode每日一题(使用最小花费爬楼梯)

2023-12-17每日一题 一、题目编号 746. 使用最小花费爬楼梯二、题目链接 点击跳转到题目位置 三、题目描述 给你一个整数数组 cost &#xff0c;其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用&#xff0c;即可选择向上爬一个或者两个台阶。 你…...

《Webpack5 升级》- Vue2.x 组件库 Webpack3 升 5

前言 基于 Vue2.x 的项目和组件库开发于 2019 年 &#xff0c;那时对 Webpack 版本没有概念&#xff0c;项目和组件库的版本混乱…有的使用 v3&#xff0c;有的使用 v4… 对于现今 2023 年&#xff08;或 2024 年&#xff09;的整个生态环境是不够用的&#xff0c;无法使用较新…...

【7K⭐】Pot:一款开源免费支持跨平台划词翻译和OCR的软件

【7K⭐】Pot&#xff1a;一款开源免费支持跨平台划词翻译和OCR的软件 如果你经常需要阅读英文文档或者图片&#xff0c;你可能会遇到以下问题&#xff1a; 浏览器自带的翻译功能翻译效果不佳&#xff0c;无法对照原文&#xff0c;而且不能翻译图片中的文字翻译插件虽然支持多…...

navicat premium历史版本下载及更新navicat premium15 永久(使用)有效期

1、navicat premium介绍 Navicat Premium 是一套可创建多个连接的数据库开发工具&#xff0c;让你从单一应用程序中同时连接 MySQL、Redis、MariaDB、MongoDB、SQL Server、Oracle、PostgreSQL 和 SQLite 。它与 GaussDB 、OceanBase 数据库及 Amazon RDS、Amazon Aurora、Amaz…...

JAVA进化史: JDK8特性及说明

JDK 8&#xff08;Java Development Kit 8&#xff09;是Java平台的一个重大版本&#xff0c;于2014年3月发布。该版本引入了许多令人期待的新特性&#xff0c;其中一些改变了Java语言的面貌&#xff0c;提供了更丰富、灵活和现代的编程体验。以下是JDK 8的一些主要特性&#x…...

vue3基础知识一,安装及使用

一、安装vue3 需要安装node&#xff0c;然后在项目所在目录命令行执行以下代码。 npm create vuelatest 回车后需要配置以下内容。 二、安装所需的依赖包并运行 cd到项目目录&#xff0c;执行以下代码安装依赖包 npm i 运行项目 npm run dev 打开浏览器查看结果 ok&#…...

3D动态路障生成

3D动态路障生成 介绍设计实现1.路面创建2.空物体的创建3.Create.cs脚本创建 总结 介绍 上一篇文章介绍了Mathf.Lerp的底层实现原理&#xff0c;这里介绍一下跑酷类游戏的动态路障生成是如何实现的。 动态路障其实比较好生成&#xff0c;但是难点在哪里&#xff0c;如果都是平面…...

Node.js--》node环境配置及nvm和nvm-desktop安装教程

博主最近换了台新电脑&#xff0c;环境得从零开始配置&#xff0c;所以以下是博主从一台纯净机中配置环境&#xff0c;绝对的小白教程&#xff0c;大家第一次安装完全可以参考我的过程&#xff0c;闲话少说&#xff0c;直接开始&#xff01;&#xff01;&#xff01; 接下来介绍…...

java的参数传递机制概述,方法重载概述,以及相关案例

前言&#xff1a; 学了Java的传递机制&#xff0c;稍微记录一下。循循渐进&#xff0c;daydayup&#xff01; java的参数传递机制概述 1&#xff0c;java的参数传递机制是什么&#xff1f; java的参数传递机制是一种值传递机制。 2&#xff0c;值传递是什么&#xff1f; 值…...