动态规划——斐波那契数列模型:面试题08.01.三步问题

文章目录

  • 题目描述
  • 算法原理
    • 1.状态表示
    • 2.状态转移方程
    • 3.初始化
    • 4.填表顺序
    • 5.返回值
  • 代码实现
    • C++
    • Java

题目描述

题目链接:面试题08.01.三步问题
在这里插入图片描述
如果n是0走法可能是1也可能是0,所以本题范围并不需要考虑直接从1开始即可
在这里插入图片描述
因为以3为结尾有直接从0到3的方式,其他的方式则需要经过前面的阶梯,所以则是基于前面的方式来计算当前位置的方式,以此类推。
PS:答案可能过大,所以题目要求需要取模1e9 + 7。

算法原理

1.状态表示

经验+题目要求:经验一般是以…开始,以…结尾。
dp[i]:表示到达i位置时,一共有多少种方式。

2.状态转移方程

dp[i] = dp[i -1] + dp[i - 2] + dp[i - 3]

3.初始化

dp[1] = 1,dp[2] = 2,dp[3] = 4

4.填表顺序

从左往右

5.返回值

dp[n]

代码实现

C++

class Solution {
public:
    int waysToStep(int n) {
        //单独处理边界条件
        if(n < 3)return n;
        else if(n == 3)return 4;
        //1.创建dp表
        vector<int> dp(n + 1);
        const int MOD = 1e9 + 7;
        //2.初始化
        dp[1] = 1,dp[2] = 2,dp[3] = 4;
        //3.填表
        for(int i = 4;i <= n;++i){
        	//处理溢出问题
            dp[i] = ((dp[i - 3] + dp[i - 2]) % MOD + dp[i - 1]) % MOD;
        }
        //4.返回值
        return dp[n];
    }
};

Java

class Solution {
    public int waysToStep(int n) {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4.返回值
        int MOD = (int) 1e9 + 7;

        // 处理⼀下边界情况
        if (n == 1 || n == 2)
            return n;
        if (n == 3)
            return 4;

        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        for (int i = 4; i <= n; i++)
        	//处理溢出问题
            dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3]) % MOD;
        return dp[n];
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/575901.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Kafka 3.x.x 入门到精通(04)——对标尚硅谷Kafka教程

Kafka 3.x.x 入门到精通&#xff08;04&#xff09;——对标尚硅谷Kafka教程 2. Kafka基础2.1 集群部署2.2 集群启动2.3 创建主题2.4 生产消息2.5 存储消息2.5.1 存储组件2.5.2 数据存储2.5.2.1 ACKS校验2.5.2.2 内部主题校验2.5.2.3 ACKS应答及副本数量关系校验2.5.2.4 日志文…

从哪些角度优化数据资产管理?详解如何将数据转化为企业持续竞争力

在上一篇文章中我们介绍了数据资产管理的诸多保障措施&#xff0c;上篇文章指路&#x1f449;如何保障数据资产管理有效开展&#xff1f;做好这几点就够了&#xff01; 本文重点将转向数据资产管理的实践。在当今这个数据驱动的时代&#xff0c;数据已成为企业最宝贵的资产之一…

使用Excel生成sql脚本(insert/update/delete)

目录 前言 一、Excel文件脚本变量 二、操作示例 前言 在系统使用初期&#xff0c;存在某种原因&#xff0c;需要对数据库数据进行批量处理操作。往往都是通过制定Excel表格&#xff0c;通过Excel导入到数据库中&#xff0c;所以就弄一个excel生成sql的导入脚本&#xff0c;希…

呼叫中心常用名词解释

ACD Automatic Call Distribution 自动呼叫分配&#xff0c;即排队。一般是用于呼叫中心的功能。在一个呼叫中心中&#xff0c;会有很多的座席来应答用户的来话&#xff0c;但是每个座席所具有的技能或者所承担的工作负荷是 不同的&#xff0c;如何根据一定的算法来保证所有的座…

C语言中浮点型存储方式

前言 这次是上次博客的续写哦&#xff0c;如果有小伙伴不了解&#xff0c;可以点击链接跳转 C语言中整数与浮点数在内存中的存储 我们在上次的博客中给大家留了一段代码&#xff0c;不知道大家现在有没有想明白呢&#xff0c;让我来为大家揭秘吧&#xff01;&#xff01; int m…

Azure AKS集群监控告警表达式配置

背景需求 Azure AKS集群中&#xff0c;需要对部署的服务进行监控和告警&#xff0c;需要创建并启用预警规则&#xff0c;而这里怎么去监控每个pod级别的CPU和内存&#xff0c;需要自己写搜索查询 解决方法 搜索和查询的语句如下&#xff0c;需要自己替换其中的部分信息,其中…

python爬虫 - 爬取html中的script数据(36kr.com新闻信息)

文章目录 1. 分析页面内容数据格式2. 使用re.findall方法&#xff0c;爬取新闻3. 使用re.search 方法&#xff0c;爬取新闻 1. 分析页面内容数据格式 打开 https://36kr.com/ 按F12&#xff08;或 在网页上右键 --> 检查&#xff08;Inspect&#xff09;&#xff09; 找…

开箱机选型攻略:如何挑选适合你的自动化设备?

在如今快节奏的生产环境中&#xff0c;自动化设备的运用已成为企业提升效率、降低成本的关键。开箱机作为自动化生产线上的重要一环&#xff0c;其选型对于企业来说至关重要。星派将为您提供一份开箱机选型攻略&#xff0c;帮助您挑选出最适合自己的自动化设备。 一、了解开箱…

18 JavaScript学习:错误

JavaScript错误 JavaScript错误通常指的是在编写JavaScript代码时发生的错误。这些错误可能是语法错误、运行时错误或逻辑错误。以下是对这些错误的一些常见分类和解释&#xff1a; 语法错误&#xff1a; 这类错误发生在代码编写阶段&#xff0c;通常是由于代码不符合JavaScrip…

Transformer模型详解01-Word Embedding

文章目录 前言Transformer 整体结构Transformer 的输入单词 Embedding原理CBOW 模型one-hot构建 CBOW 训练数据集构建 CBOW 神经网络训练 CBOW 神经网络 Skip-gram 模型one-hot构建 Skip-gram训练数据集训练 Skip-gram神经网络 Word2Vec实例数据训练保存和加载 前言 Transform…

JavaScript-Vue入门

本文主要测分享Vue的一些基础 Vue简介 Vue.js 是一个构建数据驱动的 web 界面的渐进式框架。它的主要目标是通过尽可能简单的 API 实现响应的数据绑定和组合的视图组件。 下是一些 Vue 的主要特点和概念&#xff1a; 1. 响应式数据绑定&#xff1a;Vue 使用基于 HTML 的模板语法…

文本高效拆分内容,根据空行高效拆分文本内容,文本文档管理更轻松

文本文档是我们日常生活和工作中不可或缺的一部分。然而&#xff0c;随着文本内容的不断增加&#xff0c;如何高效、有序地管理这些文档成为了一个挑战。传统的文本编辑工具往往无法满足我们对于文档整理的需求&#xff0c;而手动整理又费时费力。现在&#xff0c;我们为您带来…

【智能算法】蜉蝣算法(MA)原理及实现

目录 1.背景2.算法原理2.1算法思想2.2算法过程 3.结果展示4.参考文献 1.背景 2020年&#xff0c;K Zervoudakis等人受到自然界蜉蝣交配繁殖行为启发&#xff0c;提出了蜉蝣算法&#xff08;Mayfly Algorithm, MA&#xff09;。 2.算法原理 2.1算法思想 MA灵感来自蜉蝣交配…

“天才程序员”拼起命来有多狠?

本周 第四届ATEC科技精英赛&#xff08;ATEC2023&#xff09;线下赛——“燃烧吧&#xff01;天才程序员” 在杭州蚂蚁A空间落幕了 这个比赛同时挑战16名选手脑力和体力的上限 连续三天三夜独立答题&#xff0c;末尾淘汰、组团PK&#xff0c;吃住赛场&#xff0c;每天仅睡4…

超实用的电脑桌面便签+待办清单app

对于上班族来说&#xff0c;桌面便签加待办清单软件是提升工作效率的得力助手。想象一下&#xff0c;在繁忙的工作中&#xff0c;你能够快速记录重要事项&#xff0c;设置待办任务提醒&#xff0c;一切都能有条不紊地进行。这种便捷性&#xff0c;尤其在处理多项任务和紧急事务…

VMware17Pro虚拟机安装macOS教程(超详细)

目录 1. 前言2. 下载所需文件3. 安装VMware3.1 安装3.2 启动并查看版本信息3.3 虚拟机默认位置配置 4. 安装补丁4.1 解压补丁4.2 结束VMware相关进程4.3 运行补丁包 5. 安装macOS5.1 新建虚拟机5.2 修改虚拟机配置5.3 安装操作系统5.3.1 选择 ISO 映像文件5.3.2 开启虚拟机5.2.…

Windows上在DLL中嵌入自定义/XML文件

Windows上在DLL中嵌入自定义文件&#xff08;如&#xff1a;xml文件&#xff09; 1、前言 最近都在开发适配Genicam项目&#xff0c;在开发CTI&#xff08;Windows上可以看作DLL&#xff09;时发现需要将多个XML文件嵌入到DLL文件中方便内部代码调用。 2、前期准备 一个xml…

java接口加密解密

这里写目录标题 controller加解密工具类加密&#xff08;本质是对ResponseBody加密&#xff09;解密&#xff08;本质是对RequestBody传参解密&#xff09;注解 controller Controller public class PathVariableController {GetMapping(value "/test")ResponseBod…

【Mysql】mysql本地环境变量的配置

mysql本地环境变量的配置 1.找到Mysql的安装位置 前面步骤完成后安装好MySQL&#xff0c;为MySQL配置环境变量。MySQL默认安装在C:\Program Files下。 2.选择此电脑 右键属性 3.选择 高级系统设置 环境变量 4.配置环境变量 1)新建MYSQL_HOME变量,并配置: C:\Program Fi…

李沐-28 批量归一化【动手学深度学习v2】

记录关于批量归一化的理解&#xff0c;如有出入还请批评指正。 一、批量归一化层主要作用在以下两种情况&#xff1a; 全连接层和卷积层的输出上&#xff0c;同时要在激活函数之前还可以是全连接层和卷积层的输入上 二、关于“批量归一化对于全连接层时&#xff0c;是作用在特…