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

目录

动态规划的概念:

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

阶段:

状态:

决策:

策略:

状态转移方程:

适用的基本条件

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://xiahunao.cn/news/2774546.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

使用QT编写一个简单QQ登录界面

widget.cpp #include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this);//设置窗口标题this->setWindowTitle("QQ");//设置窗口图标this->setWindowIcon(…

k8s学习-Kubernetes的包管理器Helm

1.1 为何需要Helm Kubernetes能够很好地组织和编排容器&#xff0c;但它缺少⼀个更高层次的应用打包工具&#xff0c;而Helm就是来干这件事的。 先来看个例子。 比如对于⼀个MySQL服务&#xff0c;Kubernetes需要部署下面这些对象&#xff1a; &#xff08;1&#xff09;Serv…

three.js 箭头ArrowHelper的实践应用

效果&#xff1a; 代码&#xff1a; <template><div><el-container><el-main><div class"box-card-left"><div id"threejs" style"border: 1px solid red"></div></div></el-main></…

Golang数据库编程详解 | 深入浅出Go语言原生数据库编程

前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。点击跳转到网站https://www.captainbed.cn/kitie。 Golang学习专栏&#xff1a;https://blog.csdn.net/qq_35716689/category_12575301.html 前言 对数据库…

STM32F1 - 上电启动过程

BOOT 1> 内存映射2> 启动模式 1> 内存映射 Flash起始地址是 【0x0800 0000】 SRAM起始地址是【0x2000 0000】 2> 启动模式 STM32F103的BOOT1和BOOT0引脚&#xff0c; 决定哪块存储区&#xff0c;映射到4G内存空间【0x0000 0000】地址处。 例如 BOOT0引脚接地后&…

【云原生进阶之PaaS中间件】第三章Kafka-4.3.2-broker网络模型

1 kafka网络模型运行原理 kafka broker 在启动的时候&#xff0c;会根据你配置的listeners 初始化它的网络组件&#xff0c;用来接收外界的请求&#xff0c;这个listeners你可能没配置过&#xff0c;它默认的配置是listenersPLAINTEXT://:9092就是告诉kafka使用哪个协议&#x…

如何在 emacs 上开始使用 Tree-Sitter (archlinux)

文章目录 如何在emacs上开始使用Tree-Sitter&#xff08;archlinux&#xff09; 如何在emacs上开始使用Tree-Sitter&#xff08;archlinux&#xff09; 在archlinux上使用比windows上不知道要方便多少倍&#xff01; $ sudo pacman -S emacs $ sudo pacman -S tree-sitter这里…

containerd中文翻译系列(十五)转运服务

传输服务是一种简单灵活的服务&#xff0c;可用于在源和目的地之间传输人工制品对象。灵活的应用程序接口&#xff08;API&#xff09;允许传输接口的每个实施方案决定是否可以在源和目的地之间进行传输。这样&#xff0c;实现者就可以直接添加新功能&#xff0c;而无需对应用程…

Java算法练习4

Java算法练习4 1.1 [145. 二叉树的后序遍历](https://leetcode.cn/problems/binary-tree-postorder-traversal/)1.2 [173. 二叉搜索树迭代器](https://leetcode.cn/problems/binary-search-tree-iterator/)1.3 [98. 验证二叉搜索树](https://leetcode.cn/problems/validate-bin…

【Java数据结构】ArrayList和LinkedList的遍历

一&#xff1a;ArrayList的遍历 import java.util.ArrayList; import java.util.Iterator; import java.util.List;/*** ArrayList的遍历*/ public class Test {public static void main(String[] args) {List<Integer> list new ArrayList<>();list.add(5);list…

MySQL篇之定位与优化MySQL慢查询

一、如何定位慢查询 1.方案一&#xff1a;开源工具 调试工具&#xff1a;Arthas。 运维工具&#xff1a;Prometheus 、Skywalking。 2.方案二&#xff1a;MySQL自带慢日志 慢查询日志记录了所有执行时间超过指定参数&#xff08;long_query_time&#xff0c;单位&#xff1a;…

Filter 实现过滤符合条件的请求并落库

其他系列文章导航 Java基础合集数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 文章目录 其他系列文章导航 文章目录 前言 一、配置过滤器类 二、定义数据表、实体类、Mapper 2.1 DDL 2.2 实体类 2.3 Mapper 三、创建一个过滤器 四、实现 Nacos 配置…

分享86个行业PPT,总有一款适合您

分享86个行业PPT&#xff0c;总有一款适合您 86个行业PPT下载链接&#xff1a;https://pan.baidu.com/s/1avbzwqK8ILLWYIOylK1aRQ?pwd8888 提取码&#xff1a;8888 Python采集代码下载链接&#xff1a;采集代码.zip - 蓝奏云 学习知识费力气&#xff0c;收集整理更不易…

住宅供暖设备行业调研:市场环境将稳定发展阶段中

为使人们生活或进行生产的空间保持在适宜的热状态而设置的供热设施。 向一定的空间加热量的办法&#xff0c;可以直接把产生热量的火炉装在其中;也可以抽出其中的空气&#xff0c;加热后再送回;也可以在其中装置保持在较高温度的物体&#xff0c;向所在空间放热。这种温度较高的…

Elasticsearch:通过 ingest pipeline 对大型文档进行分块

在我之前的文章 “Elasticsearch&#xff1a;使用 LangChain 文档拆分器进行文档分块” 中&#xff0c;我详述了如何通过 LangChain 对大的文档进行分块。那个分块的动作是通过 LangChain 在 Python 中进行实现的。对于使用版权的开发者来说&#xff0c;我们实际上是可以通过 i…

【c++】模板---函数模板

1.泛型编程 如何实现一个通用的交换函数呢&#xff1f; void Swap(int& left, int& right) {int temp left;left right;right temp; } void Swap(double& left, double& right) {double temp left;left right;right temp; } void Swap(char& left,…

嵌入式学习之Linux入门篇笔记——18,makefile基本语法(下)

配套视频学习链接&#xff1a;http://【【北京迅为】嵌入式学习之Linux入门篇】 https://www.bilibili.com/video/BV1M7411m7wT/?p4&share_sourcecopy_web&vd_sourcea0ef2c4953d33a9260910aaea45eaec8 1.wildcard 函数 格式&#xff1a;$&#xff08;wildcard PAT…

爬虫系列-第一个爬虫

&#x1f308;个人主页: 会编程的果子君 ​&#x1f4ab;个人格言:“成为自己未来的主人~” 首先&#xff0c;我们需要回顾一下爬虫的概念&#xff0c;爬虫就是我们通过我们写的程序去抓取互联网上的数据资源&#xff0c;比如&#xff0c;此时我需要百度的资源&#xff0c;在不…

spring Bean生命周期 源代码分析 AbstractAutowireCapableBeanFactory createBean doCreateBean

文章目录 一、生命周期关键步骤1.1 前置条件1.2 创建bean 二、Bean生命周期、核心源码分析2.1 前置条件, 源代码2.2 创建bean, 源代码 一、生命周期关键步骤 1.1 前置条件 1.创建rootBean 生成RootBeanDefinition 2.对bean定义的方法&#xff0c;进行验证、重写 调用方法pre…

Blender教程(基础)-顶点挤出扩展-19

shiftA新建一个平面 编辑模式下&#xff0c;选中三个点&#xff0c;按X弹出按顶点删除 删除完成只剩下一个顶点 选中顶点按字母E在X轴挤出&#xff0c;按字母E在Y轴挤出 选中三个顶点按字母E延Z轴挤出 新建平面&#xff0c;按数字7到顶视图 选中顶点按E延X轴挤出 …