当前位置: 首页 > 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;但它限制了模型的…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

51c自动驾驶~合集58

我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留&#xff0c;CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制&#xff08;CCA-Attention&#xff09;&#xff0c;…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

PHP和Node.js哪个更爽?

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

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案

随着新能源汽车的快速普及&#xff0c;充电桩作为核心配套设施&#xff0c;其安全性与可靠性备受关注。然而&#xff0c;在高温、高负荷运行环境下&#xff0c;充电桩的散热问题与消防安全隐患日益凸显&#xff0c;成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI&#xff08;https://spring.io/projects/spring-ai&#xff09;作为Spring生态中的AI集成框架&#xff0c;其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似&#xff0c;但特别为多语…...