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

1.2 斐波那契数列模型:LeetCode 面试题 08.01. 三步问题


动态规划解三步问题:LeetCode 面试题 08.01. 三步问题


1. 题目链接

LeetCode 面试题 08.01. 三步问题
题目要求:小孩上楼梯,每次可以走1、2或3步,计算到达第 n 阶台阶的不同方式数,结果需对 1e9 + 7 取模。


2. 题目描述
  • 输入:整数 n,表示台阶数。
  • 输出:不同的方式数(模 1e9 + 7)。
  • 约束条件
    • 1 ≤ n ≤ 1e6
    • 结果可能超过 2^31 - 1,需取模处理。

3. 示例分析

示例 1
输入:n = 3
输出:4
解释:方式为 1+1+1, 1+2, 2+1, 3

示例 2
输入:n = 4
输出:7
解释:新增方式如 1+3, 2+2, 3+1, 1+1+2 等。


4. 算法思路
动态规划递推
  1. 状态定义
    • dp[i] 表示到达第 i 阶的方式数。
  2. 递推公式
    • dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
    • 每次可从前3个台阶走1、2或3步到达当前台阶。
  3. 初始条件
    • dp[1] = 1, dp[2] = 2, dp[3] = 4
空间优化
  • 直接使用数组存储所有状态,空间复杂度为 O(n)
  • 可优化为滚动变量(见注意事项)。

5. 边界条件与注意事项
  1. 边界处理
    • n < 4 时直接返回初始值。
  2. 取模运算
    • 每次更新状态后需立即取模,防止溢出。

6. 代码实现与解析
class Solution {
public:const int MOD = 1e9 + 7;int waysToStep(int n) {if (n == 1) return 1;if (n == 2) return 2;if (n == 3) return 4;vector<int> dp(n + 1);dp[1] = 1;dp[2] = 2;dp[3] = 4;for (int i = 4; i <= n; i++) {// 使用 long 避免中间结果溢出dp[i] = ( (long)dp[i-1] + dp[i-2] + dp[i-3] ) % MOD;}return dp[n];}
};
代码解析
  1. 初始化处理
    • 直接处理 n ≤ 3 的边界情况,返回初始值。
  2. 动态规划数组
    • dp[i] 存储到达第 i 阶的方式数,初始化前3项。
  3. 递推计算
    • 循环从 i = 4 开始,递推公式使用 long 类型防止溢出。
    • 每次计算后立即取模,确保结果合法。
  4. 返回值
    • dp[n] 即为最终结果。

优化
  1. 滚动变量优化
    • 仅保留前3个状态,空间复杂度降至 O(1)
    int waysToStep(int n) {if (n == 1) return 1;if (n == 2) return 2;if (n == 3) return 4;int a = 1, b = 2, c = 4, d;for (int i = 4; i <= n; i++) {d = ( (long)a + b + c ) % MOD;a = b;b = c;c = d;}return c;
    }
    
  2. 统一取模逻辑
    • 所有中间操作统一用 long 类型,避免隐式溢出。

总结

通过动态规划递推解决三步问题,关键点在于状态转移和取模处理。代码使用 long 类型确保大数计算正确性,适用于 n ≤ 1e6 的场景。此方法可推广至类似递推问题(如泰波那契数),需注意数值溢出和空间优化。

相关文章:

1.2 斐波那契数列模型:LeetCode 面试题 08.01. 三步问题

动态规划解三步问题&#xff1a;LeetCode 面试题 08.01. 三步问题 1. 题目链接 LeetCode 面试题 08.01. 三步问题 题目要求&#xff1a;小孩上楼梯&#xff0c;每次可以走1、2或3步&#xff0c;计算到达第 n 阶台阶的不同方式数&#xff0c;结果需对 1e9 7 取模。 2. 题目描述…...

关于AutoMapper

AutoMapper 概述 AutoMapper 是一个基于约定的对象 - 对象映射库&#xff0c;主要用于在不同对象类型之间自动映射属性值。它能根据配置的映射规则&#xff0c;将源对象的属性值填充到目标对象中&#xff0c;避免了手动编写大量繁琐的对象映射代码。 作用 提升开发效率&…...

是否每一层之间都要线性变换和激活函数?

1. 神经网络层的基本组成 一个典型的神经网络层通常包含两个步骤&#xff1a; 线性变换&#xff08;加权求和&#xff09;&#xff1a; z Wx} b 其中W 是权重矩阵&#xff0c;b是偏置向量&#xff0c;是输入&#xff0c;z 是线性输出。激活函数&#xff1a; 其中&#xff0c…...

golang 的reflect包的常用方法

目录 reflect 包方法总结 类型 (Type) 方法 值 (Value) 方法 代码示例&#xff1a; reflect 包方法总结 p : Person{Name: "小明", Age: 22}t : reflect.TypeOf(&p)v : reflect.ValueOf(p) 类型 (Type) 方法 方法名描述示例               Na…...

CentOS 7 安装 EMQX (MQTT)

CentOS 7 安装 EMQX 通过 Yum 源安装 EMQX 支持通过 Yum 源安装&#xff0c;您可通过以下 Yum 命令从中自动下载和安装 EMQX。 通过以下命令配置 EMQX Yum 源&#xff1a; curl -s https://assets.emqx.com/scripts/install-emqx-rpm.sh | sudo bash安装以下依赖项&#xff…...

Flask项目部署:Flask + uWSGI + Nginx

目录 1,网络架构 2,环境安装 2.1,安装yum:Shell软件包管理器 2.2 安装python 2.3 安装uWSGI 2.4 安装Flask 3,上传工程包到服务器,打包Flask项目 4,创建和配置 uwsgi 配置文件 uwsgi.ini 4.1配置文件 4.2配置文件注释详解 5,启动服务 6,安装nginx 7,nginx配置 8,…...

软件工程面试题(十五)

1、servlet 创建过程以及ruquest,response,session的生命周期? Servlet的创建过程: 第一步 public class AAA extends HttpServlet{ 实现对应的doxxx方法 } 第二步: 在web.xml中配置 <servlet> <servlet-name></servlet-name> <servlet-c…...

当Kafka化身抽水马桶:论组件并发提升与系统可用性的量子纠缠关系

《当Kafka化身抽水马桶&#xff1a;论组件并发提升与系统可用性的量子纠缠关系》 引言&#xff1a;一场OOM引发的血案 某个月黑风高的夜晚&#xff0c;监控系统突然发出刺耳的警报——我们的数据发现流水线集体扑街。事后复盘发现&#xff1a;Kafka集群、Gateway、Discovery服…...

python和Java的区别

Python和Java是两种流行的编程语言&#xff0c;它们之间有一些重要的区别&#xff1a; 语法&#xff1a;Python是一种动态类型的脚本语言&#xff0c;语法简洁明了&#xff0c;通常使用缩进来表示代码块。Java是一种静态类型的编程语言&#xff0c;语法更为严格&#xff0c;需要…...

QFlightInstruments飞行仪表控件库

QFlightInstruments 是一个开源的飞行仪表控件库&#xff0c;专为基于 Qt 的应用程序设计。它提供了一系列仿真实飞机仪表的组件&#xff0c;适用于飞行模拟软件、航空电子系统或任何需要高仿真飞行仪表显示的项目。 主要功能 高仿真飞行仪表&#xff1a;包括空速表、高度表、…...

可发1区的超级创新思路(python\matlab实现):MPTS+Lconv+注意力集成机制的Transformer时间序列模型

首先声明,该模型为原创!原创!原创!且该思路还未有成果发表,感兴趣的小伙伴可以借鉴! 应用场景 该模型主要用于时间序列数据预测问题,包含功率预测、电池寿命预测、电机故障检测等等。 一、模型整体架构(本文以光伏功率预测为例) 本模型由多尺度特征提取模块(MPTS)…...

Nginx — Nginx版本升级

例如&#xff1a;将10.224.11.220、10.224.11.221、10.208.11.220 三台服务器上的Nginx从1.21.1版本升级到1.23.3版本。 一、Nginx升级步骤 步骤一&#xff1a;备份老版本的Nginx&#xff08;10.224.11.220、10.224.11.221、10.208.11.220&#xff09; #关闭Nginx cd /usr/l…...

CSS学习笔记6——网页布局

目录 一、元素的浮动属性、清除浮动 清除浮动的其他方法 1、使用空标签清除浮动影响 2、使用overflow属性清除浮动 3、使用伪元素清除浮动影响 原理 overflow属性 二、元素的定位 1、相对定位 2、绝对定位 ​编辑 3、固定定位 z-index层叠等级属性 一、元素的浮动…...

C语言【指针二】

引言 介绍&#xff1a;const修饰指针&#xff0c;野指针 应用&#xff1a;指针的使用&#xff08;strlen的模拟实现&#xff09;&#xff0c;传值调用和传指调用 一、const修饰指针 1.const修饰变量 简单回顾一下前面学过的const修饰变量&#xff1a;在变量前面加上const&…...

第十六届蓝桥杯模拟二(串口通信)

由硬件框图可以知道我们要配置LED 和按键 一.LED 先配置LED的八个引脚为GPIO_OutPut,锁存器PD2也是,然后都设置为起始高电平,生成代码时还要去解决引脚冲突问题 二.按键 按键配置,由原理图按键所对引脚要GPIO_Input 生成代码,在文件夹中添加code文件夹,code中添加fun.…...

Java List 集合取交集、并集、差集、补集

在Java中&#xff0c;集合操作是编程中非常常见的需求&#xff0c;尤其是在处理数据集合时&#xff0c;如List、Set等。本文将详细介绍如何在Java中实现List集合的交集、并集、差集和补集操作&#xff0c;并提供代码示例和实现方法。 1. 交集操作 交集是指两个集合中都存在的元…...

SkyWalking+Springboot实战

1、下载SkyWalking APM 1.手动下载 Downloads | Apache SkyWalkinghttps://skywalking.apache.org/downloads/ 2.链接下载 https://dlcdn.apache.org/skywalking/10.2.0/apache-skywalking-apm-10.2.0.tar.gzhttps://dlcdn.apache.org/skywalking/10.2.0/apache-skywalking-…...

【小兔鲜】day01 项目、Vue3介绍、组合式API、小案例

【小兔鲜】day01 项目、Vue3介绍、组合式API、小案例 0. 市场上Vue前端工程师用到的技术1. Vue3小兔鲜先导课1.1 技术栈1.2 项目规模1.3 项目亮点1.4 课程安排 2. 认识Vue32.1 Vue3组合式API体验 3. create-vue创建Vue3项目3.1 新建项目结构3.2 小节3.3 补充说明npm init vuela…...

【Pandas DataFrame】

以下是 Pandas DataFrame 的核心知识点总结&#xff0c;用结构化分类帮你高效记忆关键操作和概念&#xff1a; 1. 基础操作 创建DataFrame 方法代码示例说明从字典创建df pd.DataFrame({A: [1,2], B: [3,4]})字典键为列名&#xff0c;值为数据从列表创建df pd.DataFrame([[…...

华为OD机试2025A卷 - 生成回文素数(Java Python JS C++ C )

最新华为OD机试 真题目录:点击查看目录 华为OD面试真题精选:点击立即查看 题目描述 求出大于或等于 N 的最小回文素数。 如果一个数大于 1,且其因数只有 1 和它自身,那么这个数是素数。 例如,2,3,5,7,11 以及 13 是素数。 如果一个数从左往右读与从右往左读是一…...

Jenkins教程(自动化部署)

Jenkins教程(自动化部署) 1. Jenkins是什么&#xff1f; Jenkins是一个开源的、提供友好操作界面的持续集成(CI)工具&#xff0c;广泛用于项目开发&#xff0c;具有自动化构建、测试和部署等功能。Jenkins用Java语言编写&#xff0c;可在Tomcat等流行的servlet容器中运行&…...

C#里使用libxl的对齐/边框/颜色

一份好的EXCEL文件,通道会有不同的颜色和边框来表示。 以便表示一些重要的信息,这样才能让人们一眼就看到需要关注的信息。 如下面所示: 要显示上面的内容,需要使用下面的例子: private void button12_Click(object sender, EventArgs e){var book = new ExcelBook();if…...

虚拟pinctrl驱动

之前呢&#xff0c;我们讲解了在内核中pinctrl子系统是怎么实现的&#xff0c;今天我们来尝试一下自己去写一个pinctrl子系统&#xff1a; 首先呢&#xff0c;我们来看看一个pinctrl子系统需要做的事情: 上面的话&#xff0c;我们看了一个pinctrl子系统需要的三大功能以及在驱…...

pycharm虚拟环境项目转移后配置解释器

添加解析器提示&#xff1a;无效的 Python SDK 解决方法 在到电脑安装python解析器&#xff0c;复制&#xff1a;python.exe和pythonw.exe 项目虚拟环境venv/Scripts Python解释器添加 项目现有虚拟环境&#xff0c;就可以正常使用...

蓝桥杯嵌入式学习笔记

用博客来记录一下参加蓝桥杯嵌入式第十六届省赛的学习经历 工具环境准备cubemx配置外部高速时钟使能设置串口时钟配置项目配置 keil配置烧录方式注意代码规范头文件配置 模块ledcubemx配置keil代码实现点亮一只灯实现具体操作的灯&#xff0c;以及点亮还是熄灭 按键cubemx配置k…...

0201-jsx语法基础-jsx-仿低代码平台项目

文章目录 1.jsx标签2.jsx属性3.jsx 事件3.1 声明事件3.2 使用事件&#xff08;对象&#xff09; 4. typescript类型基础4.1 类型声明4.2 事件函数传递自定义参数 5.插入js变量6. 条件判断7. 循环结语 1.jsx标签 jsx标签与html标签区别&#xff1a; 首字母大小写 大写是自定义组…...

在MCU工程中优化CPU工作效率的几种方法

在嵌入式系统开发中&#xff0c;优化 CPU 工作效率对于提升系统性能、降低功耗、提高实时性至关重要。Keil 作为主流的嵌入式开发工具&#xff0c;提供了多种优化策略&#xff0c;包括 关键字使用、内存管理、字节对齐、算法优化 等。本文将从多个方面介绍如何在 Keil 工程中优…...

Elasticsearch 的搜索功能

Elasticsearch 的搜索功能 建议阅读顺序&#xff1a; Elasticsearch 入门Elasticsearch 搜索&#xff08;本文&#xff09;Elasticsearch 搜索高级Elasticsearch 高级 1. 介绍 使用 Elasticsearch 最终目的是为了实现搜索功能&#xff0c;现在先将文档添加到索引中&#xff0c…...

【鸿蒙5.0】向用户申请麦克风授权

#效果图 步骤 在 config.json 里声明权限&#xff1a;在项目的 config.json 文件中添加麦克风权限的声明&#xff0c;告知系统应用需要使用该权限。检查权限状态&#xff1a;在代码里检查应用是否已经获得了麦克风权限。请求权限&#xff1a;若应用未获得麦克风权限&#xff0…...

数据结构与算法分析:树与哈希表(一)

遇到的问题&#xff0c;都有解决方案&#xff0c;希望我的博客能为你提供一点帮助。 一、概述 背景&#xff1a;链表处理大量数据时&#xff0c;线性访问耗时多。二叉查找树多数操作平均运行时间为 O (log N)&#xff0c;相对于链表树更加高效。 1.预备知识 1.1. 树的定义与…...

VBA第三十四期 VBA中怎么用OnKey事件

我们在VBA设计中经常需要使用到OnKey方法&#xff0c;特别是在窗口设计中比如我们想用到翻页按键&#xff0c;则就可以来建立一个OnKey事件。Setup_OnKey过程运行以后&#xff0c;就会达到最终效果&#xff0c;按PgDn键会将指针下移一行&#xff0c;按PgUp键会将指针上移一行。…...

HarmonyOS NEXT开发进阶(十五):日志打印 hilog 与 console.log 的区别

文章目录 一、前言二、两者区别对比三、HiLog 详解四、拓展阅读 一、前言 在日常开发阶段&#xff0c;日志打印是调试程序非常常用的操作&#xff0c;在鸿蒙的官方文档中介绍了hilog这种方式&#xff0c;前端转过来的开发者发现console.log也可以进行日志打印&#xff0c;而且…...

Skynet 框架中 gateserver、gate、watchdog 的关系

一、概述 在 Skynet 框架的网络通信架构中&#xff0c;gateserver、gate、watchdog 是三个核心组件&#xff0c;共同实现客户端连接的监听、管理和业务逻辑的分发。其设计目标是通过分层解耦&#xff0c;提升网络层的稳定性与业务逻辑的灵活性。 二、组件职责 1. ‌gateserve…...

第11章:优化I/O_《C++性能优化指南》_notes

第十一章核心知识点详解 11.1 读取文件的优化技巧 重点&#xff1a;减少内存分配、使用大缓冲区、优化函数调用链。 难点&#xff1a;理解系统调用开销与缓冲区大小的权衡。 代码示例与详解 示例1&#xff1a;使用高效函数签名和减少内存分配 #include <fstream> #inc…...

【C++初阶】--- 内存管理

1.C/C内存分布 我们一般说的32位机器和64位机器指的是虚拟空间的大小&#xff0c;也就是进程地址空间的大小&#xff0c;32位机器下&#xff0c;进程地址空间的大小是232个字节&#xff0c;也就是4G&#xff0c;64位机器下&#xff0c;进程地址空间的大小是264个字节,大概160亿…...

使用 Ansys Discovery 可视化液体池中的水流

了解 ANSYS Discovery&#xff1a;设计领域的变革者 ANSYS Discovery 是一款功能强大的软件工具&#xff0c;能够彻底改变设计流程。借助其先进的仿真功能&#xff0c;工程师现在可以在设计投入生产之前更深入地了解其设计。通过使用 ANSYS Discovery&#xff0c;设计师可以快…...

网络安全-网络安全基础

一、网络安全概述 TCP/IP协议定义了一个对等的开放性网络&#xff0c;使得连接到这个网络中的所有用户都可能面临来自网络中的恶意的破坏和攻击。这些攻击通过网络通信协议、网络应用协议甚至物理传输链路来实现。主要针对于软件和硬件进行攻击。那在互联网上如何保证自己的安…...

YOLOv8+ Deepsort+Pyqt5车速检测系统

该系统通过YOLOv8进行高效的目标检测与分割&#xff0c;结合DeepSORT算法完成目标的实时跟踪&#xff0c;并利用GPU加速技术提升处理速度。系统支持模块化设计&#xff0c;可导入其他权重文件以适应不同场景需求&#xff0c;同时提供自定义配置选项&#xff0c;如显示标签和保存…...

QML中的附加属性和附加信号处理程序

QML中的附加属性和附加信号处理程序 在QML中&#xff0c;附加属性(Attached Properties)和附加信号处理程序(Attached Signal Handlers)是特殊类型的属性和信号&#xff0c;它们由附加类型(Attached Types)提供&#xff0c;而不是由对象本身直接提供。 什么是附加的(Attached…...

爱普生FC-135晶振5G手机的极端温度性能守护者

在5G时代&#xff0c;智能手机不仅需要高速率与低延迟&#xff0c;更需在严寒、酷暑、振动等复杂环境中保持稳定运行。作为 5G 手机的核心时钟源&#xff0c;爱普生32.768kHz晶振FC-135凭借其宽温适应性、高精度稳定性与微型化设计&#xff0c;成为5G手机核心时钟源的理想选择&…...

GPT Workspace体验

GPT Workspace是一款将强大的自然语言处理模型&#xff08;如 ChatGPT 和 Gemini&#xff09;集成到 Google Workspace 应用&#xff08;如 Google Docs, Sheets, Slides, Gmail 和 Drive&#xff09;中的工具或插件。它的目标是提升用户在日常办公中的效率和创造力。 以下是对…...

Teleport 和 Set Actor location的区别

Teleport 和 Set Actor Location 都可以用于移动一个 Actor 的位置&#xff0c;但它们在底层逻辑和适用场景上有显著区别. 1. Set Actor Location 功能&#xff1a; 直接设置 Actor 的位置&#xff0c;不重置物理状态&#xff08;如速度、动量&#xff09;。 行为特点&#xf…...

“GPU 挤不动了?”——聊聊基于 GPU 的计算资源管理

“GPU 挤不动了?”——聊聊基于 GPU 的计算资源管理 作者:Echo_Wish “老板:为什么 GPU 服务器卡得跟 PPT 一样?” “运维:我们任务队列爆炸了,得优化资源管理!” 在 AI 训练、深度学习、科学计算的场景下,GPU 计算资源已经成为香饽饽。但 GPU 服务器贵得离谱,一台 A…...

解决前端项目中无法识别 .node 文件的依赖安装问题

解决前端项目中无法识别 .node 文件的依赖安装问题 问题描述 在 macOS 系统&#xff08;M1 Pro 芯片&#xff09;&#xff0c;使用 Node.js 版本 20.9.0 和 Vue 3 的环境下&#xff0c;项目启动过程中遇到了以下错误&#xff1a; [ERROR] No loader is configured for "…...

Gateway实战入门(四)、断言-请求头以及请求权重分流等

spring cloud-Gateway&#xff1a;断言-请求头以及请求权重分流等 一、断言Header信息要求项目前置环境要求案例一、断言-请求头信息-匹配X-Request-Id1、配置文件及代码2、测试 案例二、断言-请求头信息-匹配API版本场景主要配置信息 案例三、断言-请求头信息&#xff1a;匹配…...

YOLOv11模型的常见处理

一.数据准备&#xff1a; 1.数据集格式&#xff1a; 目录结构示例&#xff1a; datasets/├── images/│ ├── train/ # 训练图片│ └── val/ # 验证图片└── labels/├── train/ # 训练标签└── val/ # 验证标签 每张图片对应一个 .txt 标注文件…...

conda 清除 tarballs 减少磁盘占用 、 conda rename 重命名环境、conda create -n qwen --clone 当前环境

&#x1f947; 版权: 本文由【墨理学AI】原创首发、各位读者大大、敬请查阅、感谢三连 &#x1f389; 声明: 作为全网 AI 领域 干货最多的博主之一&#xff0c;❤️ 不负光阴不负卿 ❤️ 文章目录 conda clean --tarballsconda rename 重命名环境conda create -n qwen --clone …...

无线局域网

1.5G支持中低频和高频频段&#xff0c; 2.网络切片是指从应该网络中选取特定的特性和功能 3.WLAN广义指无线电波&#xff0c;激光&#xff0c;红外线等无线信号代替有线局域网中的部分或者全部传输介质所构成的网络。 4.802.11运行在2.4GHz ISM 频段&#xff0c;采用扩频通信…...

百人会上的蔚小理与「来的刚刚好」的雷军

这就是2025百人会上的蔚小理&#xff0c;努力的李斌、宣扬飞行汽车的何小鹏与大讲开源的李想。那么小米汽车的模式是什么呢&#xff1f;站在蔚小理的肩上。 这就是2025百人会上的蔚小理&#xff0c;努力的李斌、宣扬飞行汽车的何小鹏与大讲开源的李想。那么小米汽车的模式是什么…...

现代优雅杂志海报徽标设计手写英文字体安装包 Attomes – Brush Handwritten Font

Attomes 简介 – Brush 手写字体 此字体是一种精致、优雅、流畅的手写字体。它有一个美丽而独特的连字混合字母&#xff0c;因此作者用一个小漩涡嵌入来撰写它&#xff0c;从而形成现代字体&#xff0c;并准备好通过为您的下一个设计项目添加优雅和独特的风格来发表声明。将其…...