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

初识动态规划算法(题目加解析)

文章目录

  • 什么是动态规划
  • 正文
    • 力扣题
      • 第 N 个泰波那契数
      • 三步问题
      • 使用最小花费爬楼梯
  • 总结

什么是动态规划

线性动态规划:是可以用一个dp表来存储内容,并且找到规律存储,按照规律存储。让第i个位置的值等于题目要求的答案
>dp表:dp表就是用一个连续的空间存储需要存储的有规律的值。

干说无力直接正文

正文

力扣题

第 N 个泰波那契数

题目:地址
题目解析:
在这里插入图片描述

给定了三个数 T0,T1,T2
求Tn的值
**根据题意可以翻译成 Tn = Tn-1+Tn-2+Tn-**3

动态规则的题目都可以分五步
1、状态表示(★)
状态表示是必须要会的并且理解的
>一般的状态表示是:经验+题目解析
经验是要多写才能得出来的
这个题目的状态表示已经给出来了
Tn的值是前三个值的合
2、状态转移方程(★)
状态转移方程一般可以表示成 第n个值=····
题目已经给出Tn=Tn-1+Tn-2+Tn-3
3、初始化
把dp表初始化成0
4、填dp表顺序
从左往右填
5、返回值
dp[n]

代码答案:

class Solution {
public:int tribonacci(int n) {if(n==0){return 0;}if(n==1||n==2){return 1;}// vector<int> dp(n+1);// dp[0]=0,dp[1]=1,dp[2]=1;// for(int i =3;i<=n;i++)// {//     dp[i]=dp[i-1]+dp[i-2]+dp[i-3];// }//空间优化int a= 0,b=1,c=1,d=0;for(int i =3;i<=n;i++){d=a+b+c;a=b;b=c;c=d;}return d;}
};

三步问题

题目:地址
题目解析:
在这里插入图片描述
题目解释:

这个小男孩一小子可以走 1层/2层/3层
走到第n层的时候有多少种方法
如果结果太大需要%1000000007

动态规划的五步走:
1、状态表示(★)
这个题目的状态表示是
在这里插入图片描述

2、状态转移方程(★)
依照上面的解释
动态方程为Tn = Tn-1+Tn-2+Tn-3
3、初始化
初始化dp表为0
4、存储dp表的顺序
从左往右
5、返回值
dp[n]

代码:

class Solution {
public:int waysToStep(int n) {if(n==1||n==2){return n;}if(n==3){return 4;}// vector<int> dp(n+1);// dp[1] = 1,dp[2]=2,dp[3]=4;//空间优化int a =1,b=2,c=4,d=0;for(int i = 4 ;i<=n;i++){//dp[i]=((dp[i-1]+dp[i-2])%1000000007+dp[i-3])%1000000007;d=((a+b)%1000000007+c)%1000000007;a=b;b=c;c=d;}return d;}
};

使用最小花费爬楼梯

题目:地址
题目解析:
在这里插入图片描述
题目解释:

一个人一下可以走1-2步
最少需要花费多少体力到楼顶
这里的楼顶不是传过来的字符串的位置
因为如果是传过来的字符串的位置那么应该不用+他的值
但是用例1来说
10直接2步到10应该是最快的
但是解释是15
所以楼顶的位置应该在传过来字符的后一个位置

五步走:

1、状态表示
在这里插入图片描述

2、状态转移方程
方程是:dp[i]=min(cost[i-1]+dp[i-1],cost[i-2]+dp[i-2])
3、初始化
把dp表初始化
4、存入dp表的位置
从做向右
5、返回值
返回dp[i]位置的值

代码:

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {vector<int> dp(cost.size()+2);for(int i =2;i<=cost.size();i++){dp[i]=min(cost[i-1]+dp[i-1],cost[i-2]+dp[i-2]);}return dp[cost.size()];}
};

总结

这三个题的是类似的
都是用前几个数来对比或者相加
可能在解释的时候有些不好理解,作者也是刚学不久,分享一下自己的看法,喜欢的可以点点赞。

相关文章:

初识动态规划算法(题目加解析)

文章目录 什么是动态规划正文力扣题第 N 个泰波那契数三步问题使用最小花费爬楼梯 总结 什么是动态规划 线性动态规划&#xff1a;是可以用一个dp表来存储内容&#xff0c;并且找到规律存储,按照规律存储。让第i个位置的值等于题目要求的答案 >dp表&#xff1a;dp表就是用一…...

Vue2.0与Vue3.0的区别

一、Vue2和Vue3的数据双向绑定原理发生了改变 Vue2的双向数据绑定是利用ES5的一个API&#xff0c;Object.definePropert()对数据进行劫持 结合 发布 订阅模式的方式来实现的。通过Object.defineProperty来劫持数据的setter&#xff0c;getter&#xff0c;在数据变动时发布消息…...

探索人工智能领域——每日20个名词详解【day6】

目录 前言 正文 总结 &#x1f308;嗨&#xff01;我是Filotimo__&#x1f308;。很高兴与大家相识&#xff0c;希望我的博客能对你有所帮助。 &#x1f4a1;本文由Filotimo__✍️原创&#xff0c;首发于CSDN&#x1f4da;。 &#x1f4e3;如需转载&#xff0c;请事先与我联系以…...

C++初阶 | [七] string类(上)

摘要&#xff1a;标准库中的string类的常用函数 C语言中&#xff0c;字符串是以\0结尾的一些字符的集合&#xff0c;为了操作方便&#xff0c;C标准库中提供了一些str系列的库函数&#xff0c; 但是这些库函数与字符串是分离开的&#xff0c;不太符合OOP(面向对象)的思想&#…...

Django总结

文章目录 一、Web应用Web应用程序的优点Web应用程序的缺点应用程序有两种模式C/S、B/S C/S 客户端/服务端局域网连接其他电脑的MySQL数据库1.先用其他电脑再cmd命令行ping本机ip2.开放MySQL的访问 B/S 浏览器/服务端基于socket编写一个Web应用 二、Http协议1.http协议是什么2.h…...

【qml入门系列教程】:qml QtObject用法介绍

作者:令狐掌门 技术交流QQ群:675120140 博客地址:https://mingshiqiang.blog.csdn.net/ 文章目录 QtObject 是 Qt/QML 中的一个基础类型,通常用作创建一个没有 UI 的(不渲染任何东西的)纯逻辑对象。可以使用它来组织代码、存储状态或者作为属性和方法的容器。 以下是如何…...

2分图匹配算法

定义 节点u直接无边&#xff0c;v之间无边&#xff0c;边只存在uv之间。判断方法&#xff1a;BFS染色法&#xff0c;全部染色后&#xff0c;相邻边不同色 无权二部图中的最大匹配 最大匹配即每一个都匹配上min&#xff08;u&#xff0c; v&#xff09;。贪心算法可能导致&…...

[EndNote学习笔记] 导出库中文献的作者、标题、年份到Excel

菜单栏Edit中&#xff0c;选择 Output Styles 在默认的 Annotated上进行修改&#xff0c;在Bibliography栏下的Templates中修改想要导出的格式 其中&#xff0c;每个粗体标题表示&#xff0c;针对不同的文献类型&#xff0c;设置相应的导出格式。一般为Journal Article&…...

SQL Sever 基础知识 - 数据查询

SQL Sever 基础知识 - 一、查询数据 一、查询数据第1节 基本 SQL Server 语句SELECT第2节 SELECT语句示例2.1 SELECT - 检索表示例的某些列2.2 SELECT - 检索表的所有列2.3 SELECT - 对结果集进行筛选2.4 SELECT - 对结果集进行排序2.5 SELECT - 对结果集进行分组2.5 SELECT - …...

Vue入门——v-on标签

文章目录 规则v-on 一、案例总结 规则 v-on 作用&#xff1a;为html标签绑定事件语法&#xff1a; v-on&#xff1a;事件名&#xff1a;“函数名”简写为 事件名“函数名” 注意&#xff1a;函数需要定义在methods选项内部 一、案例 我们给案件绑定一个单击事件 <!DOCTYPE…...

JVM:双亲委派(未完结)

类加载 定义 一个java文件从编写代码到最终运行&#xff0c;必须要经历编译和类加载的过程&#xff0c;如下图&#xff08;图源自b站视频up主“跟着Mic学架构”&#xff09;。 编译就是把.java文件变成.class文件。类加载就是把.class文件加载到JVM内存中&#xff0c;得到一…...

Leetcode 2661. 找出叠涂元素

Leetcode 2661. 找出叠涂元素题目 给你一个下标从 0 开始的整数数组 arr 和一个 m x n 的整数 矩阵 mat 。arr 和 mat 都包含范围 [1&#xff0c;m * n] 内的 所有 整数。从下标 0 开始遍历 arr 中的每个下标 i &#xff0c;并将包含整数 arr[i] 的 mat 单元格涂色。请你找出 a…...

vscode代码调试配置

C/C代码调试 点击 vscode左侧的 run and debug&#xff0c;新建launch.json 和 tasks.json&#xff0c;并进行配置如下 launch.json {// Use IntelliSense to learn about possible attributes.// Hover to view descriptions of existing attributes.// For more informati…...

PTA 7-225 sdut-C语言实验- 冒泡排序中数据交换的次数

听说过冒泡排序么&#xff1f;一种很暴力的排序方法。今天我们不希望你用它来排序&#xff0c;而是希望你能算出从小到大冒泡排序的过程中一共进行了多少次数据交换。 输入格式: 输入数据的第一行为一个正整数 T &#xff0c;表示有 T 组测试数据。 接下来T行&#xff0c;每行…...

新的 BLUFFS 攻击导致蓝牙连接不再私密

蓝牙是一种连接我们设备的低功耗无线技术&#xff0c;有一个新的漏洞需要解决。 中间的攻击者可以使用新的 BLUFFS 攻击轻松窥探您的通信。 法国研究中心 EURECOM 的研究员 Daniele Antonioli 演示了六种新颖的攻击&#xff0c;这些攻击被定义为 BLUFFS&#xff08;蓝牙转发和…...

安全测试之推荐工具(一)

文章目录 一、前言二、Web安全&#xff08;一&#xff09;AppScan&#xff08;推荐&#xff09;&#xff08;二&#xff09;AWVS&#xff08;推荐&#xff09;&#xff08;三&#xff09;Burp Suite&#xff08;推荐&#xff09;&#xff08;四&#xff09;OWASP ZAP 三、主机安…...

final关键字

修饰 类&#xff0c;属性&#xff0c;方法&#xff0c;局部变量&#xff08;包括方法参数&#xff09; 类似c语言的const 使用方式&#xff1a; 1 不希望类被继承 用final类&#xff08;类很重要&#xff0c;担心别人重写/修改&#xff09; 2 不希望某…...

WPF MVVM模式下如何将UI窗口变量传参到Viewmodel层

WPF MVVM模式下如何将UI窗口变量传参到Viewmodel层 UI层窗口定义 //窗口中绑定ViewModel<hc:GlowWindow.DataContext><viewmodel:MainWindowViewModel /></hc:GlowWindow.DataContext>//注册初始化事件<hc:Interaction.Triggers><hc:EventTrigger…...

条款22:将成员变量声明为private

1.前言 首先&#xff0c;我们应该利用反证法&#xff0c;看看为什么成员变量不该是public&#xff0c;然后再了解所有反对public成员变量的论点同样适用于protected成员变量。最后得出一个结论&#xff1a;成员变量应该是private。 2.为什么不用public 如果成员变量不是publ…...

PTA 7-224 sdut-C语言实验-排序问题

输入10个整数&#xff0c;将它们从小到大排序后输出&#xff0c;并给出现在每个元素在原来序列中的位置。 输入格式: 输入数据有一行&#xff0c;包含10个整数&#xff0c;用空格分开。 输出格式: 输出数据有两行&#xff0c;第一行为排序后的序列&#xff0c;第二行为排序…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

Webpack性能优化:构建速度与体积优化策略

一、构建速度优化 1、​​升级Webpack和Node.js​​ ​​优化效果​​&#xff1a;Webpack 4比Webpack 3构建时间降低60%-98%。​​原因​​&#xff1a; V8引擎优化&#xff08;for of替代forEach、Map/Set替代Object&#xff09;。默认使用更快的md4哈希算法。AST直接从Loa…...

MinIO Docker 部署:仅开放一个端口

MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...

认识CMake并使用CMake构建自己的第一个项目

1.CMake的作用和优势 跨平台支持&#xff1a;CMake支持多种操作系统和编译器&#xff0c;使用同一份构建配置可以在不同的环境中使用 简化配置&#xff1a;通过CMakeLists.txt文件&#xff0c;用户可以定义项目结构、依赖项、编译选项等&#xff0c;无需手动编写复杂的构建脚本…...