浅说线性DP(上)
前言
在说线性dp之前,我们先来聊一聊动态规划是啥?
动态规划到底是啥?
动态规划是普及组内容中最难的一个部分,也是每年几乎必考的内容。它对思维的要求极高,它和图论、数据结构不同的地方在于它没有一个标准的数学表达式和明确清晰的解题方法。
动态规划是对求解最优解的一种途径,而不是一种特殊的算法。由于各种问题的性质不同,确定最优解的条件也互不相同,因而动态规划的设计方法对不同的问题,有各具特色的阶梯方法,而不存在一种万能的动态规划算法。为了方便学习,我们把若干具有代表性的动态规划问题归纳总结成不同的几类,并建立对应的数学模型。
动态规划一般用来求解多阶段决策问题的最优解,可以将过程分成若干个互相联系的阶段,在它的每一阶段都需要做决策,从而使整个过程达到最好的活动效果。各个阶段决策的选取不是任意确定的,它依赖于当前面临的状态,又影响以后的发展,当各个阶段决策确定后,就组成一个决策序列,因而也就确定了整个过程的一条活动路线。

对于动态规划问题,最重要的是分析出:
一、决策对象:我们需要对题目中的哪个变量进行决策。
二、阶段:需要将问题的全过程恰当的分成若干个相互联系的阶段,以便按一定的次序去求解。阶段的划分一般是根据时间(先后顺序) 和 空间(大小关系) 的自然特征来划分。
三、状态:某一阶段的出发位置称为状态,一个阶段可能包含多个状态,状态大多都是用 数组 来表示,即表示我们需要的答案。
四、决策:分析完问题后我们应该怎么解决问题。
五、状态转移方程:描述前一阶段到后一阶段的状态演变规律。
线性动态规划
线性动态规划是动态规划中比较简单的一类问题,他的状态转移是线性的,即状态的转移是固定的,常见的如从前到后,或者从后到前。线性动态规划和递推比较类似,在很多情况下,这两种做法大致是相同的。一般的,递推是当前要求解的答案和前面某个固定答案有关,而线性动态规划是当前答案和前面的某个答案存在关系,这个位置在不同的情况下是不相同的。
最长上升子序列
言归正传,我们继续聊线性dp。
子集和子序列和子串的区别
以 a b f s g e g s a s abfsgegsas abfsgegsas为例, f a g g a s faggas faggas是它的子集,因为子集是不计顺序的, a b g g s s abggss abggss 则是他的子序列,因为子序列是要求有顺序的,而 a b f abf abf则是他的字串
内容分析
决策对象
每个位置上的数。
阶段
共有 n n n 个数,因此有 n n n 个阶段。
状态
因为每个数都有可能是子序列的结尾,所以使用 dp[i] 表示以第 i i i 个数作为结尾的最长上升子序列的长度。
决策
如果以第 i i i 个数作为结尾,那么在这个序列中,上一个数一定要小于 a [ i ] a[i] a[i]。因此,我们需要在前面的数中找到比 a [ i ] a[i] a[i] 小的数,而且我们应该选择以这个数结尾的最长上升子序列中最长的那个,这样接在这个数后面得到的序列也是最长的。
状态转移方程
如果 h [ k ] < h [ i ] h[k]<h[i] h[k]<h[i],则 d p [ i ] = m a x ( d p [ i ] , d p [ k ] + 1 ) dp[i]=max(dp[i],dp[k]+1) dp[i]=max(dp[i],dp[k]+1),其中 k ∈ [ 1 , i − 1 ] k\in[1,i-1] k∈[1,i−1]。
最后,我们找到最大的 d p [ i ] dp[i] dp[i] 就是答案。
#include<bits/stdc++.h>
using namespace std;int a[10010],dp[10010],ans=INT_MIN;
int main(){int n;cin>>n;for (int i=1;i<=n;i++){cin>>a[i];dp[i]=1;} for (int i=1;i<=n;i++){for (int j=1;j<i;j++){if (a[j]<a[i]){dp[i]=max(dp[i],dp[j]+1);}}ans=max(ans,dp[i]);}cout<<ans;return 0;
}
相关文章:
浅说线性DP(上)
前言 在说线性dp之前,我们先来聊一聊动态规划是啥? 动态规划到底是啥? 动态规划是普及组内容中最难的一个部分,也是每年几乎必考的内容。它对思维的要求极高,它和图论、数据结构不同的地方在于它没有一个标准的数学…...
leetcode题目18
四数之和 中等 给你一个由 n 个整数组成的数组 nums ,和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] (若两个四元组元素一一对应,则认为两个四元组重复)…...
后端企业级开发之yaml数据序列化格式文件详解2024
yaml格式 数据格式 yaml 是一种数据序列化的格式 容易阅读 容易与脚本语言交互 以数据为核心 重数据轻格式 我们要知道他怎么书写 大小写敏感 属性层级关系使用多行描述 每行结尾使用冒号结束 使用缩进表示层级关系 同层级左侧对其 只运行使用空格 属性前面添加空格 #表…...
智能界面设计:数字孪生与大数据结合的美学典范
智能界面设计:数字孪生与大数据结合的美学典范 引言 在数字化浪潮的推动下,智能界面设计成为了连接用户与技术的重要桥梁。数字孪生技术与大数据的结合,不仅为UI设计带来了前所未有的创新机遇,更成为了美学与功能性融合的典范。…...
听说部门来了个00后测试开发,一顿操作给我整麻了
公司新来了个同事,听说大学是学的广告专业,因为喜欢IT行业就找了个培训班,后来在一家小公司实习半年,现在跳槽来我们公司。来了之后把现有项目的性能优化了一遍,服务器缩减一半,性能反而提升4倍!…...
Linux shell命令
cat 文件名 查看文件内容, tac文件名 倒着显示。 more 文件名 显示内容 less文件名 和more的功能一样,按上下左右键,按Q键结束。 head文件名,只显示前10行内容。 ln是一个默认创建硬链接的命令 ln 文件名 ls -i文件名…...
【Linux】Linux基本指令1
1.软件,OS,驱动 我们看看计算机的结构层次 1.1.操作系统 操作系统是一款做 软硬件管理 的软件 操作系统(计算机管理控制程序)_百度百科 (baidu.com) 操作系统(英语:Operating System,缩写&a…...
重学java 49 增强for
知之俞明,则行之越笃;行之愈笃,则知之愈益; —— 24.5.28 一、基本使用 1.作用: 遍历集合或者数组 2.格式: for(元素类型 变量名:要遍历的集合名或者数组名) 变量名就是代表的每一个元素 3.快捷键: 集合名或者数组名.for package …...
BUUCTF靶场[Web] [极客大挑战 2019]Havefun1、[HCTF 2018]WarmUp1、[ACTF2020 新生赛]Include
[web][极客大挑战 2019]Havefun1 考点:前端、GET传参 点开网址,发现是这个界面 点击界面没有回显,老规矩查看源代码,看到以下代码 代码主要意思为: 用get传参,将所传的参数给cat,如果catdog…...
现代信号处理11_Spectral Analysis谱分析(CSDN_20240526)
谱分析与傅里叶变换 对于一个信号,一方面可以从时域上对其进行分析,另一方面也可以从频域上对其进行认识,对信号进行频谱分析能够帮助我们了解能量在频域上的分布。 确定性信号的能量通常是有限的,而平稳随机信号的能量通常是无限…...
C#开发上位机应用:基础与实践
C#是一种流行的面向对象编程语言,常用于Windows应用程序的开发。上位机应用是一种用于监控和控制设备或系统的应用程序,通常与下位机(如传感器、执行器等)进行通信。在本文中,我们将介绍C#开发上位机应用的基础知识和实…...
话术巧妙分隔沟通效果更佳看看这个小技巧
客服回复客户咨询,如果遇到比较复杂的问题,经常会有大段的文字回复,用聊天宝的分段符功能,在需要分段的地方点击右上角的“插入分隔符”,就可以在指定位置分段,实现多段发送的目的。 前言 客服回复客户咨询…...
【Spring】设计模式(GOF)
Spring Framework在其架构和实现中广泛使用了多种GOF(Gang of Four)设计模式。这些设计模式帮助Spring解决了许多常见的软件开发问题,提高了代码的可重用性、可维护性和可扩展性。 1、工厂模式(Factory Pattern) 1.1简…...
php抖音详情和关键词搜索api
抖音详情和关键词搜索的 API 可以通过抖音提供的开放平台来获取。以下是使用 PHP 实现的示例代码: 获取抖音视频详情 API: 获取Key和secret请移步 <?php$accessToken YOUR_ACCESS_TOKEN; // 替换为自己的 access_token $itemId YOUR_ITEM_ID; /…...
SOCKS 代理 和 HTTP 代理
SOCKS 代理 和 HTTP 代理 的区别 SOCKS 代理 和 HTTP 代理 都是代理服务器,它们充当客户端和目标服务器之间的中介,但它们的工作方式和应用场景有所不同。 1. SOCKS 代理: 工作原理: SOCKS 代理是一种更底层的代理,…...
【Linux】自己实现一个bash进程
bash就是命令行解释器,就是Linux操作系统让我们看到的,与用户进行交互的一种外壳(shell),当然了bash也是一个进程,它有时候就是通过创建子进程来执行我们输入的命令的。这无疑就离不开我们上篇博客所说的进…...
记录深度学习GPU配置,下载CUDA与cuDnn
目标下载: cuda 11.0.1_451.22 win10.exe cudnn-11.0-windows-x64-v8.0.2.39.zip cuda历史版本网址 CUDA Toolkit Archive | NVIDIA Developer 自己下载过11.0.1版本 点击下载local版本,本地安装,有2个多GB,很大,我不喜欢network版本,容易掉线 cuDnn https://developer.nvi…...
Word将表格调成合适的大小
请等待内容完善...
2024HBCPC:C Goose Goose Duck
题目描述 Iris 有 n n n 个喜欢玩鹅鸭杀的朋友,编号为 1 ∼ n 1∼n 1∼n。 假期的时候,大家经常会在群里问有没有人玩鹅鸭杀,并且报出现在已经参与的人数。 但是每个人对于当前是否加入游戏都有自己的想法。 具体的来说,对于第…...
Llama 3 模型家族构建安全可信赖企业级AI应用之使用 Llama Guard 保护大模型对话 (八)
LlaMA 3 系列博客 基于 LlaMA 3 LangGraph 在windows本地部署大模型 (一) 基于 LlaMA 3 LangGraph 在windows本地部署大模型 (二) 基于 LlaMA 3 LangGraph 在windows本地部署大模型 (三) 基于 LlaMA…...
调用支付宝接口响应40004 SYSTEM_ERROR问题排查
在对接支付宝API的时候,遇到了一些问题,记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以? 在 Golang 的面试中,map 类型的使用是一个常见的考点,其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...
EtherNet/IP转DeviceNet协议网关详解
一,设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络,本网关连接到EtherNet/IP总线中做为从站使用,连接到DeviceNet总线中做为从站使用。 在自动…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...
LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf
FTP 客服管理系统 实现kefu123登录,不允许匿名访问,kefu只能访问/data/kefu目录,不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...
C/C++ 中附加包含目录、附加库目录与附加依赖项详解
在 C/C 编程的编译和链接过程中,附加包含目录、附加库目录和附加依赖项是三个至关重要的设置,它们相互配合,确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中,这些概念容易让人混淆,但深入理解它们的作用和联…...
Webpack性能优化:构建速度与体积优化策略
一、构建速度优化 1、升级Webpack和Node.js 优化效果:Webpack 4比Webpack 3构建时间降低60%-98%。原因: V8引擎优化(for of替代forEach、Map/Set替代Object)。默认使用更快的md4哈希算法。AST直接从Loa…...
深入理解Optional:处理空指针异常
1. 使用Optional处理可能为空的集合 在Java开发中,集合判空是一个常见但容易出错的场景。传统方式虽然可行,但存在一些潜在问题: // 传统判空方式 if (!CollectionUtils.isEmpty(userInfoList)) {for (UserInfo userInfo : userInfoList) {…...
C++实现分布式网络通信框架RPC(2)——rpc发布端
有了上篇文章的项目的基本知识的了解,现在我们就开始构建项目。 目录 一、构建工程目录 二、本地服务发布成RPC服务 2.1理解RPC发布 2.2实现 三、Mprpc框架的基础类设计 3.1框架的初始化类 MprpcApplication 代码实现 3.2读取配置文件类 MprpcConfig 代码实现…...
