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

【动态规划刷题 1 】 第N个泰波那契数 三步问题

第N个泰波那契数

链接: 第N个泰波那契数

1137 . 第 N 个泰波那契数

泰波那契序列 Tn 定义如下:
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
给你整数 n,请返回第 n 个泰波那契数 Tn 的值。

示例 1:
输入:n = 4
输出:4
解释:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

示例 2:
输入:n = 25
输出:1389537

1.状态表示

dp[i] 表示的是第 i 个泰波那契数的值。

2.状态转移方程

动态规划题,我们需要学会依靠经验和题目解析去猜测他们的状态转移方程。
这一题题目已经告诉我们了。

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

3. 初始化

从我们的递推公式可以看出, dp[i] 在 i = 0 以及 i = 1 的时候是没有办法进⾏推导的,因为dp[i-2] 或 dp[i-1] 不是⼀个有效的数据。

因此我们需要在填表之前,将0, 1, 2 位置的值初始化。题⽬中已经告诉我们
dp[0] = 0, dp[1] = dp[2] = 1 。

4. 填表顺序
按照数组下标的顺序,从左往右。

5. 返回值
应该返回 dp[n] 的值。

代码:

在写代码时按照此顺序:

  1. 创建dp
  2. 初始化
  3. 填表
  4. 返回值
   int tribonacci(int n) {vector<int> dp(n+1);if(n==0) return 0;if(n==1||n==2) return 1;dp[0]=0;dp[1]=dp[2]=1;for(int i=3;i<=n;i++){dp[i]=dp[i-1]+dp[i-2]+dp[i-3];}return dp[n];}

在这里插入图片描述

三步问题

链接: 三步问题

面试题 08.01. 三步问题

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

示例1:
输入:n = 3
输出:4
说明: 有四种走法

示例2:
输入:n = 5
输出:13

1.状态表示

dp[i] 表示的是以 i 阶楼梯为结尾,小孩跳动到此处的方式数。

2.状态转移方程

以i位置状态的最近的⼀步,来分情况讨论:
如果 dp[i] 表⽰⼩孩上第 i 阶楼梯的所有⽅式,那么它应该等于所有上⼀步的⽅式之和:

  1. 从 i-1 处跳⼀级台阶, dp[i] += dp[i - 1] ;
  2. 从 i-2 处跳两级台阶, dp[i] += dp[i - 2] ;
  3. 从 i-3 处跳三级台阶, dp[i] += dp[i - 3] ;
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

3. 初始化

从我们的递推公式可以看出, dp[i] 在 i = 0 以及 i = 1 的时候是没有办法进⾏推导的,因为dp[i-2] 或 dp[i-1] 不是⼀个有效的数据。

因此我们需要在填表之前,将0, 1, 2 位置的值初始化。我们可知
dp[1] = 1, dp[2] = 2,dp[3]=4;

4. 填表顺序
按照数组下标的顺序,从左往右。

5. 返回值
应该返回 dp[n] 的值。

代码

此题会存在数据溢出的问题,需要取模处理:

   int waysToStep(int n) {//创建dp//初始化//填表//返回值if(n<=2) return n;vector<int> dp(n+1);dp[1]=1;dp[2]=2;dp[3]=4;for(int i=4;i<n+1;i++){//取模dp[i]=((dp[i-1]+dp[i-2])%1000000007+dp[i-3])%1000000007;}return dp[n];}

在这里插入图片描述

相关文章:

【动态规划刷题 1 】 第N个泰波那契数 三步问题

第N个泰波那契数 链接: 第N个泰波那契数 1137 . 第 N 个泰波那契数 泰波那契序列 Tn 定义如下&#xff1a; T0 0, T1 1, T2 1, 且在 n > 0 的条件下 Tn3 Tn Tn1 Tn2 给你整数 n&#xff0c;请返回第 n 个泰波那契数 Tn 的值。 示例 1&#xff1a; 输入&#xff1a…...

【踩坑】三种方式解决 Homebrew failing to install - fatal: not in a git directory

问题描述 解决方法一 添加安全目录&#xff0c;没有测试。 git config --global --add safe.directory /opt/homebrew/Library/Taps/homebrew/homebrew- git config --global --add safe.directory /opt/homebrew/Library/Taps/homebrew/homebrew-cask 解决方法二 取消挂载这…...

零信任安全解决方案

什么是零信任 零信任网络架构 &#xff08;ZTNA&#xff09; 或零信任安全是一种新的组织网络安全方法。它旨在修复传统基于边界的安全性中的缺陷并简化网络设计。 它以“永不信任&#xff0c;始终验证”的原则运作。这意味着&#xff0c;无论用户或设备位于何处&#xff0c;…...

如何创建高级 CSS 下拉菜单

效果展示 实现思路及部分代码 1、定义整体页面结构 从上述的效果展示图可以看出&#xff0c;页面的整体结构应该需要一个总菜单容器来装载父级菜单项&#xff0c;并且对应的父级菜单项应该有对应的菜单子项。子菜单是分类的话&#xff0c;我们还需要额外在扩展对应的容器来装…...

java中判断list是否为空

java中判断list是否为空是日常代码中经常遇到的问题。最近发现一个Utils提供的方法可以一步判断。 废话不多说&#xff0c;直接上代码&#xff01; ArrayList<String> arrayList new ArrayList<>(); System.out.println("集合1&#xff1a;" Collecti…...

龙芯3A5000板卡在高性能工作站的应用方案-迅为电子

将龙芯3A5000应用于高性能工作站时&#xff0c;可以考虑以下方案&#xff1a; 多核计算能力&#xff1a;龙芯3A5000拥有多核心处理器&#xff0c;具备强大的计算能力。在高性能工作站中&#xff0c;可以利用多核心的处理能力来支持复杂的工程设计、科学计算和数据处理任务。…...

WebSocket心跳机制

WebSocket是HTML5开始提供的一种浏览器与服务器进行全双工通讯的网络技术&#xff0c;属于应用层协议。 WebSocket 使得客户端和服务器之间的数据交换变得更加简单&#xff0c;允许服务端主动向客户端推送数据。 1、创建webSocket // Create WebSocket connection. const sock…...

Form Generator 扩展子表单组件之表单校验(超详细)

一、form-generator是什么?✨ ⭐️ 🌟 form-generator的作者是这样介绍的:Element UI表单设计及代码生成器,可将生成的代码直接运行在基于Element的vue项目中;也可导出JSON表单,使用配套的解析器将JSON解析成真实的表单。 但目前它提供的组件并不能满足我们在项目中的…...

HTTPS安全套接字层超文本传输协议

HTTPS安全套接字层超文本传输协议 HTTPS简介HTTPS和HTTP的主要区别客户端在使用HTTPS方式与Web服务器通信时的步骤SSL/TLS协议的加密&#xff08;握手&#xff09;过程为什么数据传输阶段使用对称加密HTTPS 的优点HTTPS 的缺点HTTPS 的优化证书优化会话复用 HTTPS简介 HTTP协议…...

Jenkins发送的邮箱中没有带配置的压缩附件

【问题描述】&#xff1a;Jenkins中明明配置了邮箱发送时要带压缩附件&#xff0c;收到的邮箱中却没有附件内容 【问题定位】&#xff1a;压缩附件没有放在Jenkins工作空间下&#xff0c;所以发送的邮件并未发送附件 【解决办法】&#xff1a; 1&#xff09;把压缩附件放到J…...

VU3-02

1.一些小点 1.1 npm i -D less (安装less) -D 安装依赖到开发环境中 只在开发中生效 正式打包的时候没有它&#xff0c;只在开发时有效 1.2 父子组件传参 &#xff08;1&#xff09;子组件中定义自己的参数和事件 父传子&#xff1a;const props defineProps(["item&quo…...

Linux新手小程序——进度条

前言 目录 前言 需要先了解 1.\r和\n 2.缓冲区 一.理解字符的含义&#xff1a; 学习c语言时&#xff0c;我们可以粗略把字符分为可显字符和控制字符. 在按回车换到下一行开始的操作时&#xff0c;实际上是进行了两个操作&#xff1a;1.让光标跳到下一行&#xff08;只…...

会点C++还需要再学Python吗?

提到的C、数据结构与算法、操作系统、计算机网络和数据库技术等确实是计算机科学中非常重要的基础知识领域&#xff0c;对于软件开发和计算机工程师来说&#xff0c;它们是必备的核心知识。掌握这些知识对于开发高性能、可靠和安全的应用程序非常重要。Python作为一种脚本语言&…...

Ceph入门到精通- Linux 磁盘管理(block 与 inode)

1 硬盘 block 与 inode 详解 1.1 Sector&#xff08;扇区&#xff09;与 Block&#xff08;块&#xff09; 1&#xff09; 硬盘的最小存储单位&#xff1a;sector&#xff08;扇区&#xff09;&#xff0c;每个扇区储存 512 字节&#xff1b;操作系统会一次性连续读取多个…...

安全DNS,状态码,编码笔记整理

一 DNS DNS&#xff08;Domain Name System&#xff09;是互联网中用于将域名转换为IP地址的系统。 DNS的主要功能包括以下几个方面&#xff1a; 域名解析&#xff1a;DNS最主要的功能是将用户输入的域名解析为对应的IP地址。当用户在浏览器中输入一个域名时&#xff0c;操作…...

【业务功能篇53】Springboot 数据封装对象

Entity、VO、DTO解释 1&#xff09;Entity&#xff1a;实体&#xff0c;与数据库的每一行数据打交道的&#xff0c;它的属性对应数据库每个字段 class User{ private Long idCard; private String name; private Date birthday; ...... } 对应数据库的id&#xff0c;name&…...

将Spring Session存储到Redis中实现持久化

文章目录 Session持久化1. 添加依赖2. 配置redis连接信息3. 存储和读取session从Redis Session持久化 1. 添加依赖 在项目中添加session依赖和redis依赖&#xff0c;如下所示&#xff1a; <dependency><groupId>org.springframework.boot</groupId><art…...

Git工作中常用命令

模拟一个git完整命令流程 有一个名为 example.txt 的文本文件 Hello, this is some text.1、做一些修改并查看文件的差异&#xff1a; # 修改 example.txt 文件 echo "Hello, this is some updated text." > example.txt查看文件的差异 git diffgit diff 命令…...

【电路效应】信号处理和通信系统模型中的模拟电路效应研究(SimulinkMatlab代码实现)

目录 &#x1f4a5;1 概述 &#x1f4da;2 运行结果 &#x1f389;3 参考文献 &#x1f308;4 Matlab代码、Simulink仿真实现 &#x1f4a5;1 概述 在信号处理和通信系统模型中&#xff0c;模拟电路效应研究是指考虑到实际电路的特性对信号进行建模和分析的过程。模拟电路效应…...

Spring 的元注解

一、元注解介绍 1.1.源码引入 1.2.元注解介绍 从上面的图片可知&#xff0c;Spring 有四个【负责注解其他注解】的元注解&#xff0c;分别是&#xff1a; Target&#xff1a;标识该注解可以用于标注哪些程序元素&#xff0c;比如类、方法、字段等。 Retention&#xff1a;标…...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...

探索Selenium:自动化测试的神奇钥匙

目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障

关键领域软件测试的"安全密码"&#xff1a;Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力&#xff0c;从金融交易到交通管控&#xff0c;这些关乎国计民生的关键领域…...

第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10+pip3.10)

第一篇&#xff1a;Liunx环境下搭建PaddlePaddle 3.0基础环境&#xff08;Liunx Centos8.5安装Python3.10pip3.10&#xff09; 一&#xff1a;前言二&#xff1a;安装编译依赖二&#xff1a;安装Python3.10三&#xff1a;安装PIP3.10四&#xff1a;安装Paddlepaddle基础框架4.1…...