动态规划-斐波那契数列

一. 什么是动态规划

dp一般是需要前面状态的值的问题。比如,解决一个问题需要很多步骤,且步骤之间相关联,后一个步骤的推导需要前一个步骤的结论。而我们所做的就是,将这个带求解的问题分成若干步骤,将每个步骤答案保存,后面需要直接用即可。

二. 斐波那契数列

这类问题一般都是根据前面的状态值推导出当前的状态值

举个例子: 三步问题

题目描述: 有个小孩正在上楼梯,楼梯有n阶台阶,小孩一次可以上1阶、2阶或3阶。实现一种方法,计算小孩有多少种上楼梯的方式。结果可能很大,你需要对结果模1000000007。

题目解析: 初始给出的迈楼梯级数是: 一次可以迈1级,2级,3级:

如果有1级台阶,可以一次迈1级上去,结果就是1种上楼梯实现方式;如果有2级台阶,可以一次迈2级/两次迈1级,结果就是2种上楼梯实现方式;同理3级,可以一次迈3级/迈1级再迈2级/迈2级再迈1级/三次迈1级,结果就是4种上楼梯实现方式

设置函数: 我们设置一个dp函数,使dp[i] 存储的是i级台阶时有几种迈步方法 -》根据我们之前推导出的状态 dp[1] = 1, dp[2] = 2, dp[3] = 4

函数转移方程:那进行推导第4阶台阶应该怎么算? 我们可以先思考4阶台阶是怎么迈过来的?他可以是从3阶台阶迈1步到4阶也就是-》4-1 -》 在计算3阶台阶的方法,也就是我们初始化的 dp[3] = 4;也可以是2阶台阶迈2步到4阶也就是4-2 在计算2阶台阶的方法....所以,dp[4] = dp[3]+dp[2]+dp[1] -> dp[i] = dp[i-1]+dp[i-2]+dp[i-3];

临界值和初始化:需要初始化的就是dp的1,2,3 -》dp的长度设置为n+1; 而函数转移方程最小到i-3-》i需要从4开始

注意:对结果模1000000007-》每两个值相加后记得对结果模1000000007

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

python 去除验证码图片噪音

在处理验证码图片时,出现噪音,如横线、像素点等问题往往会影响识别率,这里给出一个去除噪音的方法,仅供学习。 import cv2 import os import numpy as np import copydef del_noise(img, number):height img.shape[0]width img…

JavaScript模块化

JavaScript模块化 一、CommonJS规范1、在node环境下的模块化导入、导出 2、浏览器环境下使用模块化browserify编译js 二、ES6模块化规范1、在浏览器端的定义和使用2、在node环境下简单使用方式一:方式二: 3、导出数据4、导入数据5、数据引用问题 一、Com…

前端:Vue学习 - 智慧商城项目

前端:Vue学习 - 智慧商城项目 1. vue组件库 > vant-ui2. postcss插件 > vw 适配3. 路由配置4. 登录页面静态布局4.1 封装axios实例访问验证码接口4.2 vant 组件 > 轻提示4.3 短信验证倒计时4.4 登录功能4.5 响应拦截器 > 统一处理错误4.6 登录权证信息存…

Mybatis学习(2)

分页 目的:减少数据的处理量 方式一:使用limit实现分页,核心SQL sql语法:select * from user limit startIndex,pageSize; 步骤: 1、接口 2、Mapper.xml 3、测试 方式二:使用注解开发 1、…

每日一题~EC168 A+B+C+D

A 题意: 字符串 每一个字符的花费是2,如果ai-1 ai ,那么ai 的花费是1. 现在可以插入一个字符,得到最大花费。输出插入字符之后的字符串。 分析:只需要在相同的连续字符中间插入一个不同的字符就可以了。如果没有连续的相同字符&am…

Python酷库之旅-第三方库Pandas(059)

目录 一、用法精讲 226、pandas.Series.pad方法 226-1、语法 226-2、参数 226-3、功能 226-4、返回值 226-5、说明 226-6、用法 226-6-1、数据准备 226-6-2、代码示例 226-6-3、结果输出 227、pandas.Series.replace方法 227-1、语法 227-2、参数 227-3、功能 …

最强开源模型 Llama 3.1 部署推理微调实战大全

目录 引言一、Llama 3.1简介二、Llama 3.1性能评估三、Llama 3.1模型推理实战1、环境准备2、安装依赖3、模型下载4、模型推理 四、Llama 3.1模型微调实战1、数据集准备2、导入依赖包3、读取数据集4、处理数据集5、定义模型6、Lora配置7、配置训练参数8、开始Trainer训练9、合并…

什么是负责任的人工智能

「AI秘籍」系列课程: 人工智能应用数学基础人工智能Python基础人工智能基础核心知识人工智能BI核心知识人工智能CV核心知识AI 进阶:企业项目实战 可直接在橱窗里购买,或者到文末领取优惠后购买: 拥有权利的同时也被赋予了重大的…

Modbus通讯协议

Modbus通讯协议 Modbus协议是一种用于电子控制器之间的通信协议,‌它允许不同类型的设备之间进行通信,‌以便进行数据交换和控制。‌Modbus协议最初为可编程逻辑控制器(‌PLC)‌通信开发,‌现已广泛应用于工业自动化领…

详细分析nohup后台运行命令

目录 1. 基本知识2. Demo 1. 基本知识 Unix/Linux 命令,用于在后台运行程序,并确保它在用户退出或注销后继续运行 nohup 的主要作用是使程序在终端会话结束后继续运行,这对需要长时间执行的任务特别有用 基本的用法如下: nohu…

3.1 拓扑排序

有向图的存储 邻接矩阵 邻接表 拓扑排序 有向无环图:不存在环的有向图 环: 在有向图中,从一个节点出发,最终回到它自身的路径被称为环 入度: 以节点x为终点的有向边的条数被称为x的入度 出度: 以节…

哈默纳科HarmonicDrive谐波减速机的使用寿命计算

在机械传动系统中,减速机的应用无处不在,而HarmonicDrive哈默纳科谐波减速机以其独特的优势,如轻量、小型、传动效率高、减速范围广、精度高等特点,成为了众多领域的选择。然而,任何机械设备都有其使用寿命&#xff0c…

数据集成是什么意思?方法有哪些?数据集成三种方法介绍

1 数据集成是什么 数据集成(Data Intergration),也称为数据整合,是通过将分布式环境中的异构数据集成起来,为用户提供统一透明的数据访问方式。该定义中的集成是指从整体层面上维护数据的一致性,并提高对数据的利用和共享&#x…

【Redis 进阶】事务

Redis 的事务和 MySQL 的事务概念上是类似的,都是把一系列操作绑定成一组,让这一组能够批量执行。 一、Redis 的事务和 MySQL 事务的区别 1、MySQL 事务 原子性:把多个操作打包成一个整体。(要么全都做,要么都不做&am…

用 Python 编写的井字游戏

一.介绍 在本文中,我将向您展示如何使用 Python 创建一个非常简单的井字游戏。 井字游戏是一种非常简单的双人游戏。因此每次只能有两个玩家玩。该游戏也称为井字游戏或 Xs 和 Os 游戏。一个玩家玩 X,另一个玩家玩 O。在这个游戏中,我们有一…

树组件 el-tree 数据回显

树组件 el-tree 数据回显 树型结构的数据回显问题&#xff1a; 这里我只放了核心代码&#xff0c;主要是如何获取选中的树节点的id集合和如何根据树节点的id集合回显数据 大家根据需要自行更改&#xff01; <el-tree ref"authorityRef" node-key"id" …

SSH访问控制:精确管理你的服务器门户

“ 在数字世界中&#xff0c;服务器的安全性是任何网络管理员的首要任务。特别是对于远程登录协议如SSH&#xff0c;确保只有授权用户可以访问是至关重要的。 今天&#xff0c;记录两种有效的方法来控制用户对特定服务器的访问&#xff1a;通过sshd_config实现黑/白名单机制和利…

【Python】pandas:替换值、添加行/列,删除行/列,更改形状(含数据透视表)

pandas是Python的扩展库&#xff08;第三方库&#xff09;&#xff0c;为Python编程语言提供 高性能、易于使用的数据结构和数据分析工具。 pandas官方文档&#xff1a;User Guide — pandas 2.2.2 documentation (pydata.org) 帮助&#xff1a;可使用help(...)查看函数说明文…

前端面试宝典【HTML篇】【4】

欢迎来到《前端面试宝典》,这里是你通往互联网大厂的专属通道,专为渴望在前端领域大放异彩的你量身定制。通过本专栏的学习,无论是一线大厂还是初创企业的面试,都能自信满满地展现你的实力。 核心特色: 独家实战案例:每一期专栏都将深入剖析真实的前端面试案例,从基础知…

【区块链+绿色低碳】山东邹平:区块链生态环境监管平台 | FISCO BCOS应用案例

山东省滨州市生态环境局邹平分局通过实地考察和调研发现&#xff0c;执法大队在执法工作中存在各排污企业设备系统无 法互通、终端采集数据固证难且可信度低、环境执法电子证据采集规则与司法采信标准不统一等痛点。而区块链 的分布式记账、不易篡改性和智能合约自动执行机制&a…