备战蓝桥杯---动态规划(理论基础)

目录

动态规划的概念:

解决多阶段决策过程最优化的一种方法

阶段:

状态:

决策:

策略:

状态转移方程:

适用的基本条件

1.具有相同的子问题

2.满足最优子结构

3.满足无后效性

动态规划的实现方式:


动态规划的概念:

解决多阶段决策过程最优化的一种方法

阶段:

把问题分成几个相互联系的有顺序的环节。

状态:

某一阶段的出发位置

决策:

从某一状态演变到下一个状态的选择

策略:

从开始到终点的决策序列。

状态转移方程:

从i到i+1状态的演变规律。

适用的基本条件

1.具有相同的子问题

(1)保证这个问题可以分解成几个子问题并且可以用他们来解决这个问题。

(2)这些子问题也可以分解成相同的子问题。

2.满足最优子结构

问题的最优解包含着他的子问题的最优解,即此后决策必须基于上一次产生的最优决策。

举个栗子:

假如A是当前的最优策略,那么,我们要保证下一次的最优解一定是在A的基础上产生的,而不能是由当前的不是最优的策略导出的。

其实,动态规划是一种分阶段贪心的过程,我们要确保最长远的利益来自于每一步当前的最优利益。

就像这一题,我们选一个路径使他们的和%4最小,显然,如果我们只求当前%4的最小值,无法推出来下一步的最优解。

像这样的情况,我们可以重新考虑状态转移方程,我们发现,每一个余数都有存在的价值,于是我们可以把存在的余数记下来,再用他们去求下一个状态。

3.满足无后效性

要包含所有影响答案的因素,即它用于解决当前问题与过去状态无关的问题

举个例子:

大家应该都写过走楼梯的递归问题。a[i]=a[i-1]+a[i-2]。但是,如果有这么一个规定:走过50楼的人不能再走100楼,显然这样子在100楼时,我们不知道前面的99与98是否走过。

于是,我们应该再记录一个值表示是否踏过50,

我们不妨记f[i][0]为没有上过50,f[i][1]为上过50,这样的话,我们在i<50前用f[i][0]=f[i-1][0]+f[i-2][0]; f[i][1]=0;

i==50: f[50][0]=0,f[50][1]=f[49][0]+f[48][0],

i>50&&i<100: f[i][0]=f[i-1][0]+f[i-2][0],f[i][1]=f[i-1][1]+f[i-2][0];

i==100:f[100][0]=f[99][0]+f[98][0],f[100][1]=0;

i>100:f[i][0]=f[i-1][0]+f[i-2][0];f[i][1]=f[i-1][0]+f[i-2][0];

动态规划的实现方式:

1.递推(直接用for循环)

2.记忆化搜索

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

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

相关文章

电路设计(16)——纪念馆游客进出自动计数显示器proteus仿真

1.设计要求 设计、制作一个纪念馆游客进出自动计数显示器。 某县&#xff0c;有一个免费参观的“陶渊明故里纪念馆”&#xff0c;游客进出分道而行&#xff0c;如同地铁有确保单向通行的措施。在入口与出口处分别设有红外检测、声响、累加计数器装置&#xff0c;当游人进&#…

CentOS 安装 redis 7.2

nginx官网 https://redis.io/download/ 把鼠标放到这里&#xff0c;复制下载地址 在服务器找个文件夹执行命令 wget https://github.com/redis/redis/archive/7.2.4.tar.gz tar -zxvf 7.2.4.tar.gz make make install 看到这几行就说明安装成功了 不放心的话再查看下b…

docker安装、运行

1、安装 之前有docker的话&#xff0c;需要先卸载旧版本&#xff1a; sudo yum remove docker \docker-client \docker-client-latest \docker-common \docker-latest \docker-latest-logrotate \docker-logrotate \docker-engine 安装之前需要安装yum工具&#xff1a; sud…

UE5 播放本地MP3、MP4

1.创建一个媒体播放器 2.如创建视频&#xff0c;勾选。 它会多一个媒体纹理给你 3.1 设置音频 在一个actor上添加“媒体音频组件” “音频媒体播放器”赋值给它 3.2播放音频 添加一个音频媒体播放器变量&#xff0c; 赋值 地址使用绝对地址 4.1设置视频 UI上创建一个imag…

【MySQL】MySQL函数学习和总结

&#x1f308;个人主页: Aileen_0v0 &#x1f525;热门专栏: 华为鸿蒙系统学习|计算机网络|数据结构与算法 ​&#x1f4ab;个人格言:“没有罗马,那就自己创造罗马~” #mermaid-svg-Ny0xnYjfHqF7s3aS {font-family:"trebuchet ms",verdana,arial,sans-serif;font-siz…

一周学会Django5 Python Web开发-Django5操作命令

锋哥原创的Python Web开发 Django5视频教程&#xff1a; 2024版 Django5 Python web开发 视频教程(无废话版) 玩命更新中~_哔哩哔哩_bilibili2024版 Django5 Python web开发 视频教程(无废话版) 玩命更新中~共计11条视频&#xff0c;包括&#xff1a;2024版 Django5 Python we…

[UI5 常用控件] 08.Wizard,NavContainer

文章目录 前言1. Wizard1.1 基本结构1.2 属性1.2.1 Wizard&#xff1a;complete1.2.2 Wizard&#xff1a;finishButtonText1.2.3 Wizard&#xff1a;currentStep1.2.4 Wizard&#xff1a;backgroundDesign1.2.5 Wizard&#xff1a;enableBranching1.2.6 WizardStep&#xff1a;…

VTK 三维场景的基本要素(相机) vtkCamera

观众的眼睛好比三维渲染场景中的相机&#xff0c;在VTK中用vtkCamera类来表示。vtkCamera负责把三维场景投影到二维平面&#xff0c;如屏幕&#xff0c;相机投影示意图如下图所示。 1.与相机投影相关的要素主要有如下几个&#xff1a; 1&#xff09;相机位置: 相机所处的位置…

HTTP基本概念-HTTP 是什么?

资料来源 : 小林coding 小林官方网站 : 小林coding (xiaolincoding.com) HTTP 是什么? HTTP 是超文本传输协议&#xff0c;也就是HyperText Transfer Protocol。 能否详细解释「超文本传输协议」? HTTP 的名字「超文本协议传输」&#xff0c;它可以拆成三个部分: 超文本传输…

融资项目——获取树形结构的数据

如下图所示&#xff0c;下列数据是一个树形结构数据&#xff0c;行业中包含若干子节点。表的设计如下图&#xff0c;设置了一个id为1的虚拟根节点。&#xff08;本树形结构带虚拟根节点共三层&#xff09; 实现逻辑&#xff1a; 延时展示方法&#xff0c;先展现第二层的信息&a…

【原创 附源码】Flutter安卓及iOS海外登录--Google登录最详细流程

最近接触了几个海外登录的平台&#xff0c;踩了很多坑&#xff0c;也总结了很多东西&#xff0c;决定记录下来给路过的兄弟坐个参考&#xff0c;也留着以后留着回顾。更新时间为2024年2月8日&#xff0c;后续集成方式可能会有变动&#xff0c;所以目前的集成流程仅供参考&#…

论文阅读——MP-Former

MP-Former: Mask-Piloted Transformer for Image Segmentation https://arxiv.org/abs/2303.07336 mask2former问题是&#xff1a;相邻层得到的掩码不连续&#xff0c;差别很大 denoising training非常有效地稳定训练时期之间的二分匹配。去噪训练的关键思想是将带噪声的GT坐标…

【Make编译控制 01】程序编译与执行

目录 一、编译原理概述 二、编译过程分析 三、编译动静态库 四、执行过程分析 一、编译原理概述 make&#xff1a; 一个GCC工具程序&#xff0c;它会读 makefile 脚本来确定程序中的哪个部分需要编译和连接&#xff0c;然后发布必要的命令。它读出的脚本&#xff08;叫做 …

Android CMakeLists.txt语法详解

一.CMake简介 你或许听过好几种 Make 工具&#xff0c;例如 GNU Make &#xff0c;QT 的 qmake &#xff0c;微软的 MSnmake&#xff0c;BSD Make&#xff08;pmake&#xff09;&#xff0c;Makepp&#xff0c;等等。这些 Make 工具遵循着不同的规范和标准&#xff0c;所执行的…

ansible shell模块 可以用来使用shell 命令 支持管道符 shell 模块和 command 模块的区别

这里写目录标题 说明shell模块用法shell 模块和 command 模块的区别 说明 shell模块可以在远程主机上调用shell解释器运行命令&#xff0c;支持shell的各种功能&#xff0c;例如管道等 shell模块用法 ansible slave -m shell -a cat /etc/passwd | grep root # 可以使用管道…

四、机器学习基础概念介绍

四、机器学习基础概念介绍 1_机器学习基础概念机器学习分类1.1 有监督学习1.2 无监督学习 2_有监督机器学习—常见评估方法数据集的划分2.1 留出法2.2 校验验证法&#xff08;重点方法&#xff09;简单交叉验证K折交叉验证&#xff08;单独流出测试集&#xff09;&#xff08;常…

Android用setRectToRect实现Bitmap基于Matrix矩阵scale缩放RectF动画,Kotlin(一)

Android用setRectToRect实现Bitmap基于Matrix矩阵scale缩放RectF动画&#xff0c;Kotlin&#xff08;一&#xff09; 基于Matrix&#xff0c;控制Bitmap的setRectToRect的目标RectF的宽高。从很小的宽高开始&#xff0c;不断迭代增加setRectToRect的目标RectF的宽高&#xff0c…

IDEA Ultimate下载(采用JetBrain学生认证)

IDEA Ultimate版本下载 Ulitmate是无限制版&#xff08;解锁所有插件&#xff0c;正版需要付费。学生可以免费申请许可&#xff09;Community是开源社区版本&#xff08;部分插件不提供使用&#xff0c;比如Tomcat插件。免费&#xff09; 我们将通过学生认证获取免费版。 Je…

Tied Block Convolution: 具有共享较薄滤波器的更简洁、更出色的CNN

摘要 https://arxiv.org/pdf/2009.12021.pdf 卷积是卷积神经网络&#xff08;CNN&#xff09;的主要构建块。我们观察到&#xff0c;随着通道数的增加&#xff0c;优化后的CNN通常具有高度相关的滤波器&#xff0c;这降低了特征表示的表达力。我们提出了Tied Block Convolutio…

利用YOLOv8 pose estimation 进行 人的 头部等马赛克

文章大纲 马赛克几种OpenCV 实现马赛克的方法高斯模糊pose estimation 定位并模糊:三角形的外接圆与膨胀系数实现实现代码实现效果参考文献与学习路径之前写过一个文章记录,怎么对人进行目标检测后打码,但是人脸识别有个问题是,很多人的背影,或者侧面无法识别出来人脸,那…