【动态规划】01第 N 个泰波那契数(easy)

2023-11-30 19:44

本文主要是介绍【动态规划】01第 N 个泰波那契数(easy),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接 :leetcode第 N 个泰波那契数

目录

题目解析:

算法原理

1.状态表示

2.状态转移方程

3.初始化

4.填表顺序

5.返回值

编写代码


题目解析:

题目让我们求第n个数的泰波那契数。

由题可得:

我们可以把它改写为:

接着我们举几个例子,带入上面的公式来分析:

我们可以得到,当我们想得到当前位置的值就需要将前三个位置的值相加就可以得到;


算法原理:

1.状态表示

先创建一个dp表

首先先思考dp表里面的值所表示的含义(是什么?)

由上面的分析我们可以知道,我们可以用dp[i]来表示在第i处的泰波那契数为dp[i];

这种状态表示怎么来的?

1.题目要求

题目要求算出在n处的泰波那契数,所以算出dp[n]就可得出结果;

2.状态转移方程

dp[i]等于什么?

由上面的分析:

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

3.初始化

(保证填表的时候不越界)

从上面的dp[i]公式,我们发现当i=0、1、2时等号后面的dp[i-1]、dp[i-2]、dp[i-3]会越界

所以我们这里需要将i=0、1、2初始化,并在写代码时在前面先条件判断;

4.填表顺序

(为了填写当前状态的时候,所需要的状态已经计算过了)

这里所需要的状态是:dp[i-1]、dp[i-2]、dp[i-3];

这几个数都是在i之前的,

所以我们这里是从左向右填表;

5.返回值

(根据题目要求和状态表示)

综上分析:

返回为:dp[n]


编写代码:

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

这篇关于【动态规划】01第 N 个泰波那契数(easy)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

一文详解SpringBoot中控制器的动态注册与卸载

《一文详解SpringBoot中控制器的动态注册与卸载》在项目开发中,通过动态注册和卸载控制器功能,可以根据业务场景和项目需要实现功能的动态增加、删除,提高系统的灵活性和可扩展性,下面我们就来看看Sp... 目录项目结构1. 创建 Spring Boot 启动类2. 创建一个测试控制器3. 创建动态控制器注

springboot如何通过http动态操作xxl-job任务

《springboot如何通过http动态操作xxl-job任务》:本文主要介绍springboot如何通过http动态操作xxl-job任务的问题,具有很好的参考价值,希望对大家有所帮助,如有错... 目录springboot通过http动态操作xxl-job任务一、maven依赖二、配置文件三、xxl-

Java调用C#动态库的三种方法详解

《Java调用C#动态库的三种方法详解》在这个多语言编程的时代,Java和C#就像两位才华横溢的舞者,各自在不同的舞台上展现着独特的魅力,然而,当它们携手合作时,又会碰撞出怎样绚丽的火花呢?今天,我们... 目录方法1:C++/CLI搭建桥梁——Java ↔ C# 的“翻译官”步骤1:创建C#类库(.NET

MyBatis编写嵌套子查询的动态SQL实践详解

《MyBatis编写嵌套子查询的动态SQL实践详解》在Java生态中,MyBatis作为一款优秀的ORM框架,广泛应用于数据库操作,本文将深入探讨如何在MyBatis中编写嵌套子查询的动态SQL,并结... 目录一、Myhttp://www.chinasem.cnBATis动态SQL的核心优势1. 灵活性与可

Mybatis嵌套子查询动态SQL编写实践

《Mybatis嵌套子查询动态SQL编写实践》:本文主要介绍Mybatis嵌套子查询动态SQL编写方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言一、实体类1、主类2、子类二、Mapper三、XML四、详解总结前言MyBATis的xml文件编写动态SQL

SpringBoot实现Kafka动态反序列化的完整代码

《SpringBoot实现Kafka动态反序列化的完整代码》在分布式系统中,Kafka作为高吞吐量的消息队列,常常需要处理来自不同主题(Topic)的异构数据,不同的业务场景可能要求对同一消费者组内的... 目录引言一、问题背景1.1 动态反序列化的需求1.2 常见问题二、动态反序列化的核心方案2.1 ht

golang实现动态路由的项目实践

《golang实现动态路由的项目实践》本文主要介绍了golang实现动态路由项目实践,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习... 目录一、动态路由1.结构体(数据库的定义)2.预加载preload3.添加关联的方法一、动态路由1

Python Selenium动态渲染页面和抓取的使用指南

《PythonSelenium动态渲染页面和抓取的使用指南》在Web数据采集领域,动态渲染页面已成为现代网站的主流形式,本文将从技术原理,环境配置,核心功能系统讲解Selenium在Python动态... 目录一、Selenium技术架构解析二、环境搭建与基础配置1. 组件安装2. 驱动配置3. 基础操作模

使用easy connect之后,maven无法使用,原来需要配置-Djava.net.preferIPv4Stack=true问题

《使用easyconnect之后,maven无法使用,原来需要配置-Djava.net.preferIPv4Stack=true问题》:本文主要介绍使用easyconnect之后,maven无法... 目录使用easGWowCy connect之后,maven无法使用,原来需要配置-DJava.net.pr

慢sql提前分析预警和动态sql替换-Mybatis-SQL

《慢sql提前分析预警和动态sql替换-Mybatis-SQL》为防止慢SQL问题而开发的MyBatis组件,该组件能够在开发、测试阶段自动分析SQL语句,并在出现慢SQL问题时通过Ducc配置实现动... 目录背景解决思路开源方案调研设计方案详细设计使用方法1、引入依赖jar包2、配置组件XML3、核心配