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

动态规划详解(完结篇)——如何抽象出动态规划算法?以及解题思路

今天直接开始讲解

FIRST:如何抽象出动态规划算法?

这个问题,困扰了无数代OIER,包括本蒟蒻

在比赛的时候,看一道题,怎么想到他是什么算法的呢?

这就需要抽象能力

而不同的算法,往往有着不同的特点

就来说说动态规划的题目特点

  1. 通过遍历,能够把所有的情况考虑到。这一点同样适合于递归

  1. 有可能存在重叠性的子问题。没错,这一点也适用于递归

有的同学就问了

那动态规划和递归不是同样的特点吗?

回到蒟蒻写的动态规划1

里面说过,动态规划是可以用递归代替的

也就是说,如果你的状态转移方程真的实在绞尽脑汁费劲九牛二虎之力也想不出来,就用递归来做

但代价就是也许拿不到满分

SECOND:解题思路

动态规划抽象出状态之后,就要进行遍历每一个状态

  1. 抽象状态

  1. 初始化

  1. 确定循环起始以及边界

  1. 写出状态转移方程

  1. 输出

  1. return 0;

大概就是上述这个过程了

每日例题:

题目描述
辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同的草药,采每一株都需要一些时间,每一株也有它自身的价值。我会给你一段时间,在这段时间里,你可以采到一些草药。如果你是一个聪明的孩子,你应该可以让采到的草药的总价值最大。”
如果你是辰辰,你能完成这个任务吗?
输入格式
第一行有 22 个整数 �T(1≤�≤10001≤T≤1000)和 �M(1≤�≤1001≤M≤100),用一个空格隔开,�T 代表总共能够用来采药的时间,�M 代表山洞里的草药的数目。
接下来的 �M 行每行包括两个在 11 到 100100 之间(包括 11 和 100100)的整数,分别表示采摘某株草药的时间和这株草药的价值。
输出格式
输出在规定的时间内可以采到的草药的最大总价值。
输入输出样例
输入 #1复制
70 3 71 100 69 1 1 2
输出 #1复制
3
说明/提示
【数据范围】
对于 30%30% 的数据,�≤10M≤10;
对于全部的数据,�≤100M≤100。

一个纯纯的01背包模板

  1. 抽象状态:f[i]表示第i分钟采到的最大价值

  1. 初始化:no

  1. 确定循环起始以及边界:第一层循环1到m,第二层循环t到0(真的是01背包模板,看不懂的可以借鉴一下上一篇文章)

  1. 写出状态转移方程:dp[j]=max(dp[j-w[i]]+val[i], dp[j]);如果采了这个药,那么就要用当前时间减去采药的时间,也就是采药之前需要的时间加上现在的状态

  1. 输出(见代码)

真正做题时,大家也可以按照这个顺序,非常的清晰

那么有的同学就要问了:状态定义有什么规律吗?

  1. 首先,我们先创建一个数组,f数组,假设他是一维的,然后去想这个一维状态表示什么(简单多了)

  1. 就假设是一维,尝试写状态转移方程

  1. 如果发现,写不通了,也就是有更多的情况表示不出来

  1. 增加维度

然后循环上述操作

但是遇到很难的题,还得是靠智商,因为难的动态规划不仅仅要抽象出来

更需要你优化,也就是减少维度

来迟的AC代码:


# include <iostream>
# include <cstdio>
using namespace std;
int w[105], val[105];
int dp[1005];
int main(){int t,m;    scanf("%d%d",&t,&m);for(int i=1;i<=m;i++){scanf("%d%d",&w[i],&val[i]);}for(int i=1;i<=m;i++) {for(int j=t;j>=0;j--) {if(j>=w[i]){dp[j]=max(dp[j-w[i]]+val[i], dp[j]);}}}    printf("%d",dp[t]);return 0;
}


这会动态规划系列就真的结束了

这次讲算法比之前真的费了更大的力气,更多的时间,更多的键盘()

所以希望各位佬能够点个免费的赞

如果动态规划方面还有什么不明白的,随时私信我

我可以出番外篇()

这篇文章到这里就结束了

再见

相关文章:

动态规划详解(完结篇)——如何抽象出动态规划算法?以及解题思路

今天直接开始讲解FIRST&#xff1a;如何抽象出动态规划算法&#xff1f;这个问题&#xff0c;困扰了无数代OIER&#xff0c;包括本蒟蒻在比赛的时候&#xff0c;看一道题&#xff0c;怎么想到他是什么算法的呢&#xff1f;这就需要抽象能力而不同的算法&#xff0c;往往有着不同…...

C语言一维数组篇【下】——每日刷题经验分享

一维数组篇——每日刷题经验分享~&#x1f60e;前言&#x1f64c;有序序列插入一个整数 &#x1f60a;序列中删除指定数字 &#x1f60a;序列中整数去重小乐乐查找数字筛选法求素数总结撒花&#x1f49e;&#x1f60e;博客昵称&#xff1a;博客小梦~ &#x1f60a;最喜欢的座右…...

VHDL语言基础-组合逻辑电路-其它组合逻辑模块

目录 多路选择器&#xff1a; 逻辑功能&#xff1a; 常用的类型&#xff1a; 4选1多路选择器的实现&#xff1a; 求补器&#xff1a; 求补器的实现&#xff1a; 三态门&#xff1a; 三态门的应用实例&#xff1a; 三态门的实现&#xff1a; 缓冲器&#xff1a; 什么是…...

初识Vue

文章目录1. 前言2. Vue 的特点3. 安装 Vue4. HelloWord1. 前言 vue是什么 &#xff1f; 引用 &#xff1a; vue.js 文档   Vue (读音 /vjuː/&#xff0c;类似于 view) 是一套用于构建用户界面的渐进式框架。与其它大型框架不同的是&#xff0c;Vue 被设计为可以自底向上逐层…...

TOUGH系列软件建模实践方法及在地下水、CO2地质封存、水文地球化学、地热等多相多组分系统多过程耦合

查看原文>>> https://mp.weixin.qq.com/s?__bizMzAxNzcxMzc5MQ&mid2247578057&idx7&sn75f8d2c1c6edb28af76a8db4bb773de3&chksm9be2aed9ac9527cf0081082cdcf781e6c37f9f3ba383332ed1116abcbee0f05c0593187e964d&token2070450548&langzh_CN#r…...

Codeforces Round #699 (Div. 2)

E. 题意:n本书,每本书有颜色a[i],一次操作可以将其中一本书放在末尾,求满足:相同颜色的书都是相邻的 的最小操作次数. 显然最多只需要n次,考虑能节省多少次.倒着考虑,记f[i]为i~n最多能节约的次数.先预处理出每种颜色的出现的位置范围l[i],r[i]. 1.不节约这本书f[i] f[i 1]…...

MySQL存储过程的传参和流程控制

目录 一.存储过程传参—in 演示 二.存储过程传参—out 演示 三.存储过程传参—inout 演示 四.流程控制—判断 格式 演示 五.流程控制—case 语法 演示 六.流程控制—循环 循环—while 循环—repeat 循环—loop 一.存储过程传参—in in表示传入的参数&#xff0c;可以传…...

MySQl学习(从入门到精通11)

MySQl学习&#xff08;从入门到精通11&#xff09;第 14 章_视图1. 常见的数据库对象2. 视图概述2. 1 为什么使用视图&#xff1f;2. 2 视图的理解3. 创建视图3. 1 创建单表视图3. 2 创建多表联合视图3. 3 基于视图创建视图4. 查看视图5. 更新视图的数据5. 1 一般情况5. 2 不可…...

关于ThreadLocal

弱引用 1.1 java中的各种引用和测试: https://blog.csdn.net/thewindkee/article/details/102723838 1.2 treadlocal中的弱引用测试: https://blog.csdn.net/thewindkee/article/details/103726942 (这篇很重要) 内存泄露: https://zhuanlan.zhihu.com/p/523628871 综合考虑 …...

【C++】类和对象(中)

文章目录1. 类的6个默认成员函数2. 构造函数概念特性3. 析构函数概念特性4. 拷贝构造函数概念特征5. 运算符重载5.1 前置和后置重载5.2 赋值运算符重载6. 日期类的实现7. const成员8. 取地址及const取地址操作符重载1. 类的6个默认成员函数 如果一个类中什么成员都没有&#x…...

js下载文件

url为文件的src地址 url必须符合同源策略或者url的接口地址允许跨域&#xff0c;否则浏览器会报跨域错误 axios.get(data.url ,{ responseType: ‘blob’, }) .then( response>{ let blob new Blob([response.data]); let url window.URL.createObjectURL(blob); // 创建 …...

ESP8266 + STC15+ I2C OLED带网络校时功能的定时器时钟

ESP8266 + STC15+ I2C OLED带网络校时功能的定时器时钟 📍相关篇《ESP8266 + STC15基于AT指令通过TCP通讯协议获取时间》 📌ESP8266 AT固件基于安信可AT固件,相关刷AT固件可以参考《NodeMCU-刷写AT固件》 🔖STC15 单片机采用的是:STC15F2K60S2 晶振频率采用内部:22.11…...

计算机入门基础知识大全

♥️作者&#xff1a;小刘在C站 ♥️个人主页&#xff1a;小刘主页 ♥️每天分享云计算网络运维课堂笔记&#xff0c;努力不一定有收获&#xff0c;但一定会有收获加油&#xff01;一起努力&#xff0c;共赴美好人生&#xff01; ♥️夕阳下&#xff0c;是最美的&#xff0c;绽…...

Python程序出现错误怎么办?

Python 异常处理 python提供了两个非常重要的功能来处理python程序在运行中出现的异常和错误。你可以使用该功能来调试python程序。 异常处理: 本站Python教程会具体介绍。 断言(Assertions):本站Python教程会具体介绍。 python标准异常 异常名称 描述 BaseException 所有异常…...

【Vue3】v-if和v-for优先级

&#x1f388;博客主页&#xff1a;&#x1f308;我的主页&#x1f308; &#x1f388;欢迎点赞 &#x1f44d; 收藏 &#x1f31f;留言 &#x1f4dd; 欢迎讨论&#xff01;&#x1f44f; &#x1f388;本文由 【泠青沼~】 原创&#xff0c;首发于 CSDN&#x1f6a9;&#x1f…...

Windows上实现 IOS 自动化测试

本文介绍如何使用tideviceWDAairtest/facebook-wda实现在Windows上进行IOS APP自动化测试 环境准备 Windows Python环境 Python 3.6 WebDriverAgent安装 下载最新的项目到Mac&#xff1a;https://github.com/appium/WebDriverAgent $ git clone https://github.com/appiu…...

Linux云服务器下怎么重置MySQL8.0数据库密码

文章目录一、修改my.cnf配置文件为mysql免登陆二、免密登陆mysql三.给root用户重置密码1、首先查看当前root用户相关信息&#xff0c;在mysql数据库的user表中2、把root密码置为空3、退出mysql&#xff0c;删除/etc/my.cnf文件中添加进去的skip-grant-tables 重启mysql服务4、使…...

JVM调优

JVM调优-VisualVmVisualVm/ Jconsule远程连接第一种方式第二种方式&#xff1a;java 11开启远程GC连接如果还连不上考虑防火墙拦截了端口firewall-cmd --list-all,查看一下并暴露对应端口连接配置VisualVm界面简介采集GC信息的一些命令垃圾回收器切换VisualVm/ Jconsule远程连接…...

【配电网规划】SOCPR和基于线性离散最优潮流(OPF)模型的配电网规划( DNP )(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

锦正茂EM3电磁铁的技术参数

产品特点&#xff1a; ※U形结构、视野开阔、磁场强度高、磁场强度大小调节方便 ※体积小、重量轻、占空比小、结构紧凑、磁场性能更佳 ※电磁铁的工作气隙调节轻便灵活&#xff0c;极头处设有螺纹&#xff0c;更换极头装卸方便 ※可选配工作间隙刻度指示 ※小气隙时用于铁…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互

物理引擎&#xff08;Physics Engine&#xff09; 物理引擎 是一种通过计算机模拟物理规律&#xff08;如力学、碰撞、重力、流体动力学等&#xff09;的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互&#xff0c;广泛应用于 游戏开发、动画制作、虚…...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...