算法---动态规划

动态规划

  • 1.前言
  • 2. 示例 - 第N个泰波那契数
    • 2.1 算法原理(重点)
    • 2.2 代码
  • 3. 总结解题思路

1.前言

哪些情况下会用到动态规划:

1.最优化问题:当需要求解最大值或最小值的问题时,可以考虑使用动态规划。例如,最长递增子序列、最短路径问题等。

2.问题具有重叠子问题性质:如果问题的解可以由其子问题的解构成,并且子问题之间存在重叠,即同一个子问题会被多次求解,那么可以使用动态规划。通过将子问题的解保存下来,避免重复计算,提高效率。

3.问题具有最优子结构性质:如果问题的最优解可以由其子问题的最优解推导得出,那么可以使用动态规划。通过递推关系式,将问题分解为子问题,并利用子问题的最优解来构造原问题的最优解。

4.求解过程具有重叠子结构性质:如果问题的求解过程中,需要多次用到相同的中间结果,那么可以使用动态规划。通过保存中间结果,避免重复计算,提高效率。

5.多阶段决策问题:当问题可以划分为多个阶段,并且每个阶段的决策依赖于之前阶段的决策结果时,可以使用动态规划。通过定义状态和状态转移方程,逐步求解每个阶段的最优解。

2. 示例 - 第N个泰波那契数

题目地址:点这里

在这里插入图片描述

2.1 算法原理(重点)

在这里插入图片描述
空间优化(选):

  • 背包问题
  • 滚动数组

在这里插入图片描述


1. 创建一个长度为38的数组arr,用于存储计算过程中的中间结果。数组的下标表示泰波那契数的序号,数组元素存储对应序号的泰波那契数的值。

2. 初始化数组的前三个元素arr[0]、arr[1]和arr[2]分别为0、1、1,这是泰波那契数列的起始值。

3. 如果n小于等于2,直接返回arr[n],即泰波那契数列的前三个数。

4. 从i=3开始,通过循环填充数组arr的剩余元素。对于每个i,计算泰波那契数arr[i]的值,它等于前三个数的和arr[i-3] + arr[i-2] + arr[i-1]。

5. 循环结束后,数组arr中的所有泰波那契数都已计算得到。

6. 返回arr[n],即第n个泰波那契数的值。


2.2 代码

class Solution {
public:int tribonacci(int n) {//1.创建dp表int arr[38]={0};//2.初始化arr[0]=0,arr[1]=1,arr[2]=1;if(n<=2) return arr[n];int temp=0;//3.填表for(int i=3;i<=n;i++){temp=arr[i-3]+arr[i-2]+arr[i-1];arr[i]=temp;}//4.返回值return arr[n];}
};

3. 总结解题思路


  1. 状态表示
  2. 状态转移方程
  3. 初始化
  4. 填表顺序
  5. 返回值

在这里插入图片描述

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

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

相关文章

[C语言]——内存函数

目录 一.memcpy使用和模拟实现&#xff08;内存拷贝&#xff09; 二.memmove 使用和模拟实现 三.memset 函数的使用&#xff08;内存设置&#xff09; 四.memcmp 函数的使用 C语言中规定&#xff1a; memcpy拷贝的就是不重叠的内存memmove拷贝的就是重叠的内存但是在VS202…

SecureCRT:高效安全的远程连接工具

SecureCRT是一款功能强大的终端仿真工具&#xff0c;主要用于连接和运行包括Windows、UNIX和VMS在内的远程系统。它支持多种协议&#xff0c;如SSH1、SSH2、Telnet、SFTP、Rlogin、Serial、SCP等&#xff0c;确保用户与目标设备之间的通信安全&#xff0c;并防止网络攻击和窥探…

Android Preference简单介绍

Android Preference简单介绍 文章目录 Android Preference简单介绍一、前言二、Preference 简单介绍二、PreferenceScreen和SwitchPreference 简单示例2、相关demo代码示例&#xff08;1&#xff09;SettingsActivity.Java&#xff08;2&#xff09;layout\settings_activity.x…

局域网内的手机、平板、电脑的文件共享

在日常工作生活中&#xff0c;经常需要将文件在手机、平板、电脑间传输&#xff0c;以下介绍三种较为便捷的方法&#xff1a; 1.LocalSend 该软件是免费开源的&#xff0c;可以在局域网内的任意手机、平板、电脑间传递文件&#xff0c;并且任意一方都可以作为“发送方”和“接…

taro框架之taro-ui中AtSwipeAction的使用

题记&#xff1a;所需效果&#xff1a;滑动删除 工作进程 官网文档代码 <AtSwipeAction options{[{text: 取消,style: {backgroundColor: #6190E8}},{text: 确认,style: {backgroundColor: #FF4949}} ]}><View classNamenormal>AtSwipeAction 一般使用场景</…

DataEase大屏iframe嵌入自建网站(React)

1、修改dataease 所在的服务器nginx配置 server {listen 80;server_name dataease.ibaiqiu.cn;return 307 https://$host$request_uri; } server {listen 443 ssl;server_name dataease.ibaiqiu.cn;client_max_body_size 30M;ssl_certificate /usr/local/nginx/co…

计算机三级——网络技术(综合题第二题)

路由器工作模式 用户模式 当通过Console或Telnet方式登录到路由器时&#xff0c;只要输入的密码正确&#xff0c;路由器就直接进入了用户模式。在该模式下&#xff0c;系统提示符为一个尖括号(>)。如果用户以前为路由器输入过名称&#xff0c;则该名称将会显示在尖指号的前…

HarmonyOS应用开发实战 - Api9 拍照、拍视频、选择图片、选择视频、选择文件工具类

鸿蒙开发过程中&#xff0c;经常会进行系统调用&#xff0c;拍照、拍视频、选择图库图片、选择图库视频、选择文件。今天就给大家分享一个工具类。 1.话不多说&#xff0c;先展示样式 2.设计思路 根据官方提供的指南开发工具类&#xff0c;基础的拍照、拍视频、图库选照片、选…

分布式组件 Nacos

1.在之前的文章写过的就不用重复写。 写一些没有写过的新东西 2.细节 2.1命名空间 &#xff1a; 配置隔离 默认&#xff1a; public &#xff08;默认命名空间&#xff09;:默认新增所有的配置都在public空间下 2.1.1 开发 、测试 、生产&#xff1a;有不同的配置文件 比如…

计算联合体union的大小

一&#xff1a;联合类型的定义 联合也是一种特殊的自定义类型&#xff0c;这种类型定义的变量也包含一系列的成员&#xff0c;特征是这些成员公用同一块空间&#xff08;所以联合也叫共用体&#xff09; 比如&#xff1a;共用了 i 这个较大的空间 二&#xff1a; 联合的特点 …

【热门话题】ECMAScript vs JavaScript:理解两者间的联系与区别

&#x1f308;个人主页: 鑫宝Code &#x1f525;热门专栏: 闲话杂谈&#xff5c; 炫酷HTML | JavaScript基础 ​&#x1f4ab;个人格言: "如无必要&#xff0c;勿增实体" 文章目录 ECMAScript vs JavaScript&#xff1a;理解两者间的联系与区别1. ECMAScript&am…

智慧工地解决方案,智慧工地项目管理系统源码,支持大屏端、PC端、手机端、平板端

智慧工地解决方案依托计算机技术、物联网、云计算、大数据、人工智能、VR&AR等技术相结合&#xff0c;为工程项目管理提供先进技术手段&#xff0c;构建工地现场智能监控和控制体系&#xff0c;弥补传统方法在监管中的缺陷&#xff0c;最线实现项目对人、机、料、法、环的全…

mysql 如何设计分库分表

在MySQL中设计分库分表的方法通常涉及到水平拆分与垂直拆分两种主要方式。 水平拆分&#xff1a; 按照某一列进行水平拆分&#xff1a; 可以根据某一列&#xff08;如用户ID、时间等&#xff09;的取值范围将数据拆分到不同的数据库或表中。基于哈希值的水平拆分&#xff1a;…

Linux 创建交换空间

&#x1f680; 作者主页&#xff1a; 有来技术 &#x1f525; 开源项目&#xff1a; youlai-mall &#x1f343; vue3-element-admin &#x1f343; youlai-boot &#x1f33a; 仓库主页&#xff1a; Gitee &#x1f4ab; Github &#x1f4ab; GitCode &#x1f496; 欢迎点赞…

百度智能云+SpringBoot=AI对话【人工智能】

百度智能云SpringBootAI对话【人工智能】 前言版权推荐百度智能云SpringBootAI对话【人工智能】效果演示登录AI对话 项目结构后端开发pom和propertiessql_table和entitydao和mapperservice和implconfig和utilLoginController和ChatController 前端开发css和jslogin.html和chat.…

【xr806开发板使用】连接wifi例程实现

##开发环境 win10 WSL ##1、环境配置 参考&#xff1a;https://aijishu.com/a/1060000000287513 首先下载安装wsl 和ubuntu https://docs.microsoft.com/zh-cn/windows/wsl/install &#xff08;1&#xff09;安装repo&#xff1a; 创建repo安装目录&#xff1a; mkdir ~/…

.NET Framework 服务实现监控可观测性最佳实践

环境信息 系统环境&#xff1a;Windows Server开发语言&#xff1a;.NET Framework > 4.6.1APM探针包&#xff1a;ddtrace 准备工作 安装 Datakit 主机部署&#xff1a; 主机安装 - 观测云文档 打开采集 APM 采集器 Windows 主机配置 # 到如下路径&#xff0c;把ddtr…

sqlalchemy和moke生成实体类(一)

前言 如果通过java生成实体类&#xff0c;可以通过mybatis或者mybatis-plus的generator。 而sqlalchemy也可以生成实体类&#xff0c;通过sqlalcodegen或者flask-sqlalcodegen。 使用flask-sqlalcodegen生成实体类 建表 建立学生表&#xff0c;如下。 create table stude…

Chrome 114 带着侧边栏扩展来了

效果展示 manifest.json {"manifest_version": 3,"name": "ChatGPT学习","version": "0.0.2","description": "ChatGPT,GPT-4,Claude3,Midjourney,Stable Diffusion,AI,人工智能,AI","icons"…

linux系统------------Mysql数据库介绍、编译安装

目录 一、数据库基本概念 1.1数据(Data) 1.2表 1.3数据库 1.4数据库管理系统(DBMS) 数据库管理系统DBMS原理 1.5数据库系统&#xff08;DBS) 二、数据库发展史 1、第一代数据库 2、第二代数据库 3、第三代数据库 三、关系型数据库 3.1关系型数据库应用 3.2主流的…