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

C++算法-青蛙跳台阶【面试】

"青蛙跳台阶"问题是一个经典的递归问题,也与斐波那契数列有关。问题是这样的:一只青蛙站在一个n阶台阶上,它每次可以跳1阶或2阶,问青蛙跳到顶端总共有多少种跳法。

这个问题可以用递归或动态规划来解决。以下是使用C++实现的动态规划解法:

#include <iostream>
#include <vector>// 动态规划解法
int climbStairs(int n) {if (n <= 2) {return n;}// 创建一个数组来存储子问题的解std::vector<int> dp(n + 1, 0);// 初始化前两个台阶的跳法dp[1] = 1;dp[2] = 2;// 计算从3阶到n阶的跳法for (int i = 3; i <= n; ++i) {dp[i] = dp[i - 1] + dp[i - 2];}// 返回n阶台阶的跳法总数return dp[n];
}int main() {int n = 5;std::cout << "Number of ways to climb " << n << " steps is: " << climbStairs(n) << std::endl;return 0;
}

这段代码中,climbStairs函数使用了一个std::vector<int>来存储子问题的解,避免了重复计算。数组dp[i]表示到达第i阶台阶的跳法数。根据题目条件,到达第i阶台阶的跳法数等于到达(i-1)阶和(i-2)阶台阶的跳法数之和。

面试回答示例:
"青蛙跳台阶问题可以通过动态规划来解决。我们首先定义一个数组dp,其中dp[i]表示到达第i阶台阶的跳法数。我们知道到达第一阶和第二阶都只有一种方法。对于更高的台阶,到达那里的方法数是到达前一阶和前两阶台阶的方法数之和,因为青蛙可以选择从这两个位置跳过来。我们从第三阶台阶开始,逐步计算直到第n阶,最终返回dp[n]作为答案。这种方法避免了递归方法中的重复计算,时间复杂度是O(n),空间复杂度也是O(n)。"

相关文章:

C++算法-青蛙跳台阶【面试】

"青蛙跳台阶"问题是一个经典的递归问题&#xff0c;也与斐波那契数列有关。问题是这样的&#xff1a;一只青蛙站在一个n阶台阶上&#xff0c;它每次可以跳1阶或2阶&#xff0c;问青蛙跳到顶端总共有多少种跳法。 这个问题可以用递归或动态规划来解决。以下是使用C实…...

px转rem插件postcss-plugin-px2rem使用方法(浏览器缩放页面自适应)

px转rem插件postcss-plugin-px2rem使用方法&#xff08;浏览器缩放页面自适应&#xff09; 1. 常见屏幕自适应的布局 百分比布局rem布局css媒体查询在前端框架设计初期&#xff0c;应优先选择好页面布局方式 2. postcss-plugin-px2rem插件的使用 官网地址&#xff1a;https…...

批量文件重命名技巧:轻松替换删除文件夹名中的字母,实现高效文件管理新境界

在数字化时代&#xff0c;我们每天都会面对大量的文件和文件夹。无论是工作文档、学习资料还是个人收藏&#xff0c;文件命名的规范性都显得尤为重要。然而&#xff0c;手动一个一个去修改文件名&#xff0c;不仅耗时耗力&#xff0c;还容易出错。那么&#xff0c;有没有一种方…...

windows设备/路由设备上ip地址如何查看、使用

在Windows设备上查看本地IP地址&#xff08;IPv4和IPv6&#xff09;&#xff1a; 使用命令提示符&#xff1a; 打开命令提示符&#xff08;在Windows中按Win R&#xff0c;然后输入"cmd"并按Enter&#xff09;。在命令提示符窗口中&#xff0c;输入以下命令以查看…...

服务端⾼并发分布式结构演进之路

在进行技术学习过程中&#xff0c;由于大部分读者没有经历过一些中大型系统的实际经验&#xff0c;导致无法从全局理解一些概念&#xff0c;所以本文以一个"电子商务"应用为例&#xff0c;介绍从一百个到千万级并发情况下服务端的架构的演进过程&#xff0c;同时列举…...

Stable Diffusion ProtoVisionXL大模型之艺术盛宴!

今天基于ProtoVisionXL这款大模型为大家呈现一些视觉上的艺术盛宴,视觉冲击宣传海报信手拈来&#xff0c;再配上你的宣传语&#xff0c;妥妥地让人眼前一亮。 实测参数&#xff1a; 分辨率&#xff1a;768*1024 采样方法 (Sampler)&#xff1a;DPM 2M Karras 迭代步数 (Ste…...

浅谈golang字符编码

1、 Golang 字符编码 Golang 的代码是由 Unicode 字符组成的&#xff0c;并由 Unicode 编码规范中的 UTF-8 编码格式进行编码并存储。 Unicode 是编码字符集&#xff0c;囊括了当今世界使用的全部语言和符号的字符。有三种编码形式&#xff1a;UTF-8&#xff0c;UTF-16&#…...

Vite和Webpack的区别是什么,你站队谁?

Vite和Webpack有很多相同之处&#xff0c;也有区别&#xff0c;很多老铁分不清&#xff0c;贝格前端工场借助此文为大家详细介绍一下。 一、关于Vite和Webpack Vite和Webpack都是前端开发中常用的构建工具&#xff0c;用于将源代码转换为可在浏览器中运行的静态资源。它们在一…...

【微信小程序】事件传参的两种方式

文章目录 1.什么是事件传参2.data-*方式传参3.mark自定义数据 1.什么是事件传参 事件传参:在触发事件时&#xff0c;将一些数据作为参数传递给事件处理函数的过程&#xff0c;就是事件传参 在微信小程序中&#xff0c;我们经常会在组件上添加一些自定义数据&#xff0c;然后在…...

前端针对需要递增的固定数据

这里递增的是1到12 data(){return{cycleOptions:Array.from({ length: 12 }, (v, k) > ({value: k 1,label: String(k 1)})),} }<el-select v-model"ruleForm.monthLength" placeholder"请选择周期数量"><el-optionv-for"item in cycle…...

红酒保存中的氧气管理:适度接触与避免过度氧化

在保存云仓酒庄雷盛红酒的过程中&#xff0c;我们不得不面对一个微妙的问题&#xff1a;氧气管理。氧气&#xff0c;这个我们生活中无处不在的气体&#xff0c;对于红酒的保存却有着至关重要的影响。适度接触氧气对红酒的陈年过程和品质维护具有积极作用&#xff0c;然而过度氧…...

从零开始搭建开源智慧城市项目(三)上升线效果

前言 上一节实现了添加建筑物线框&#xff0c;模型外墙和道路地面材质添加。这一节准备通过简单的shader实现上升线效果。 思路 简单的说一下思路&#xff0c;通过获取模型顶点坐标所在的高度Z来进行筛选&#xff0c;高度再某一区间内设置成上升线的颜色&#xff0c;其余高度…...

unity基础(五)地形详解

目录 一 创建地形 二 调整地形大小 三 创建相邻地形 四 创建山峰 五 创建树木 七 添加风 八 添加水 简介: Unity 中的基础地形是构建虚拟场景的重要元素之一。 它提供了一种直观且灵活的方式来创建各种地形地貌&#xff0c;如山脉、平原、山谷等。 通过 Unity 的地形…...

postman接口测试工具详解

Postman 是一个功能强大的 API 开发和测试工具&#xff0c;广泛应用于开发人员和测试人员进行 API 的调试、测试、文档生成等工作。以下是对 Postman 的详细介绍。 1. 功能概览 1.1 请求构建 请求类型: 支持 GET、POST、PUT、DELETE、PATCH、OPTIONS 等多种 HTTP 方法。URL …...

2024年护网行动全国各地面试题汇总(3)作者:————LJS

应急响应基本思路和流程 收集信息&#xff1a;收集客户信息和中毒主机信息&#xff0c;包括样本判断类型&#xff1a;判断是否是安全事件&#xff0c;何种安全事件&#xff0c;勒索、挖矿、断网、DoS 等等抑制范围&#xff1a;隔离使受害⾯不继续扩⼤深入分析&#xff1a;日志分…...

计算机专业的学生要达到什么水平才能进入大厂工作?越早知道越好

计算机专业的学生要达到什么水平才能进入BAT等大厂工作&#xff1f;越早知道越好. 一、算法题 各大公司笔试、面试基本都考这个&#xff0c;别的不说&#xff0c;《剑指Offer》所有题目背下来&#xff0c;Leetcode高频题目刷个一两百遍&#xff0c;搞过ACM也可以&#xff0c;…...

巡检费时费力?试试AI自动巡检

随着企业IT规模不断增长&#xff0c;设备、系统越来越多&#xff0c;运维工作压力也与日俱增。保障设备、系统健康稳定地运行&#xff0c;日常巡检是运维工作不可或缺的部分。通过巡检可以及时发现设备、系统的异常问题&#xff0c;提前预防及时处理&#xff0c;避免问题扩大产…...

46-4 等级保护 - 网络安全等级保护概述

一、网络安全等级保护概述 原文:没有网络安全就没有国家安全 二、网络安全法 - 安全立法 中华人民共和国主席令 第五十三号 《中华人民共和国网络安全法》已于2016年11月7日由中华人民共和国第十二届全国人民代表大会常务委员会第二十四次会议通过,并自2017年6月1日起正式…...

css引入方式有几种?link和@import有什么区别?

在CSS中&#xff0c;引入外部样式表的方式主要有两种&#xff1a;<link>标签和import规则。 使用<link>标签引入外部样式表&#xff1a; <link rel"stylesheet" href"path/to/style.css">这种方式是在HTML文档的<head>部分或者…...

使用‘消除’技术绕过LLM的安全机制,不用训练就可以创建自己的nsfw模型

开源的大模型在理解和遵循指令方面都表现十分出色。但是这些模型都有审查的机制&#xff0c;在获得被认为是有害的输入的时候会拒绝执行指令&#xff0c;例如会返回“As an AI assistant, I cannot help you.”。这个安全功能对于防止误用至关重要&#xff0c;但它限制了模型的…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

中医有效性探讨

文章目录 西医是如何发展到以生物化学为药理基础的现代医学&#xff1f;传统医学奠基期&#xff08;远古 - 17 世纪&#xff09;近代医学转型期&#xff08;17 世纪 - 19 世纪末&#xff09;​现代医学成熟期&#xff08;20世纪至今&#xff09; 中医的源远流长和一脉相承远古至…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)

漏洞概览 漏洞名称&#xff1a;Apache Flink REST API 任意文件读取漏洞CVE编号&#xff1a;CVE-2020-17519CVSS评分&#xff1a;7.5影响版本&#xff1a;Apache Flink 1.11.0、1.11.1、1.11.2修复版本&#xff1a;≥ 1.11.3 或 ≥ 1.12.0漏洞类型&#xff1a;路径遍历&#x…...

Windows安装Miniconda

一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...

MySQL 部分重点知识篇

一、数据库对象 1. 主键 定义 &#xff1a;主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 &#xff1a;确保数据的完整性&#xff0c;便于数据的查询和管理。 示例 &#xff1a;在学生信息表中&#xff0c;学号可以作为主键&#xff…...