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

动态规划问题 -- 多状态模型(买股票的最佳时机II)

目录

  • 动态规划分析问题五步曲
  • 题目概述
  • 利用状态机推导状态转移方程式
  • 代码编写

动态规划分析问题五步曲

不清楚动态规划分析问题是哪关键的五步的少年们可以移步到
链接: 动态规划算法基础
这篇文章非常详细的介绍了动态规划算法是如何分析和解决问题的

题目概述

链接: 买股票的最佳时机II
在这里插入图片描述

  1. 状态表示(题目要求+自己的经验)
    本题状态:分析第i个位置,发现在第i个位置我们可以处于可买入或可卖出状态
    所以本题应该有两个状态表示
    buy[i] : 表示第i个位置为可买入状态(即在i位置时没持有股票)可获得的最大利润
    sell[i] : 表示第i个位置为可出售状态(即在i位置时持有股票)可获得的最大利润

利用状态机推导状态转移方程式

再推导状态转移方程式之前,不妨列出所有状态之间的转换关系
这些状态之间的转换关系,就被称之为状态机

本题 可买入和可卖出状态的状态机如下

在这里插入图片描述

  1. 状态转移方程推导
    对i位置进行分类讨论,再配合状态机的使用
    当i位置为可买入状态,第i-1个位置可能为可买入状态或可卖出状态
    当i位置为可卖出状态,第i-1个位置可能为可买入状态或可卖出状态
    (要注意从可买入状态可卖出状态可卖出状态可买入状态的转换)
    在这里插入图片描述
  1. 初始化(防止越界+结合状态表示初始化)
    根据状态转移方程,当i = 0时会发生越界
    根据状态表示 :
    buy[0] : 要使得第一个位置为可买入状态,那么不买入股票就行 buy[0] = 0;
    sell[0] : 要使得第一个位置为可卖出状态,那么一定要买入第一份股票 sell[0] = 0-prices[0] ;
  1. 填表顺序(分析要填i位置前一个依赖状态的位置)
    本题两个dp表显然都是从左到右填表
  1. 返回值(由题目要求来)
    最后一个位置处于可卖出状态,一定不是最大利润
    buy[m-1] > sell[m-1] 恒成立,所以最后返回的是 buy[m-1] ;

代码编写

有了动态规划五步曲我们就可以写出非常优雅的代码了

 int maxProfit(vector<int>& prices) {int n = prices.size();if(n == 0) return 0;vector<int> buy(n);auto sell = buy;auto ice = buy;sell[0] -= prices[0];for(int i = 1 ; i < n ; i++){buy[i] = max(buy[i-1],ice[i-1]);sell[i] = max(buy[i-1]-prices[i],sell[i-1]);ice[i] = sell[i-1] + prices[i];}return max(ice[n-1],buy[n-1]);}

少年,今天你又进步了一点点哟,明天继续加油吧
在这里插入图片描述

相关文章:

动态规划问题 -- 多状态模型(买股票的最佳时机II)

目录 动态规划分析问题五步曲题目概述利用状态机推导状态转移方程式代码编写 动态规划分析问题五步曲 不清楚动态规划分析问题是哪关键的五步的少年们可以移步到 链接: 动态规划算法基础 这篇文章非常详细的介绍了动态规划算法是如何分析和解决问题的 题目概述 链接: 买股票的最…...

【落羽的落羽 C++】进一步认识模板

文章目录 一、非类型模板参数二、模板的特化1. 函数模板特化2. 类模板特化 三、模板的编译分离 一、非类型模板参数 模板参数可以分为类型参数和非类型参数。我们之前使用的都是类型参数&#xff0c;即出现在模板参数列表中&#xff0c;跟在class或typename之类的参数类型名称…...

Java爬虫能处理京东商品数据吗?

Java爬虫完全可以处理京东商品数据。通过Java爬虫技术&#xff0c;可以高效地获取京东商品的详细信息&#xff0c;包括商品名称、价格、图片、描述等。这些信息对于市场分析、选品上架、库存管理和价格策略制定等方面具有重要价值。以下是一个完整的Java爬虫示例&#xff0c;展…...

#跟着若城学鸿蒙# web篇-初探

前言 先看下官方介绍&#xff0c;这里总结了比较重要的几点Web组件基础&#xff1a;加载与渲染网页全面解析Web组件是现代应用开发中不可或缺的重要元素&#xff0c;它允许开发者在原生应用中无缝集成Web内容。本文将全面介绍Web组件的基本功能&#xff0c;包括多种内容加载方…...

Top-p采样:解锁语言模型的创意之门

Top - p采样 是什么&#xff1a;核采样&#xff1a;排序&#xff0c;累计到0.7&#xff0c;随机选择 在自然语言生成和大规模语言模型推理中&#xff0c;Top - p采样&#xff08;又叫核采样&#xff0c;Nucleus Sampling&#xff09;是一种基于累积概率的采样策略。 Top - p介…...

周赛好题推荐

这周周赛很有质量的&#xff0c;上了一个很有意思的数学题目&#xff0c;推了半天..... 给定一个区间[l,r]&#xff0c;求出区间内所有满足x mod 2^i !k的所有正整数&#xff08;最后全部进行异或&#xff09; 首先我们不妨先算出[l,r]区间所有数字的异或&#xff0c;然后在算…...

【RabbitMQ】实现RPC通信的完整指南

文章目录 RPC 通信创建相关队列客户端代码声明队列发送请求接收响应完整代码 服务端代码设置同时只能获取一个消息接收消息完整代码 运行程序启动客户端启动服务端 RPC 通信 RPC (Remote Procedure Call), 即远过程调用。它是一种通过网络从远程计算机上请求服务&#xff0c;而…...

CK3588下安装linuxdeployqt qt6 arm64

参考资料&#xff1a; Linux —— linuxdeployqt源码编译与打包&#xff08;含出错解决&#xff09; linux cp指令报错&#xff1a;cp: -r not specified&#xff1b; cp: omitting directory ‘xxx‘&#xff08;需要加-r递归拷贝&#xff09; CMake Error at /usr/lib/x86_64…...

滑动窗口之二(优先队列)

原本滑动窗口的板子用的是数组和双指针模拟&#xff0c;我嫌麻烦还不好懂找了双端队列。但其实还是不太好使&#xff0c;比如今天的这道题就处理起来很麻烦。但是如果用优先队列的话就可以一直保证整个窗口是有序的&#xff0c;只需判断一下是否在窗口内即可。但是&#xff01;…...

小刚说C语言刷题—1088求两个数M和N的最大公约数

1.题目描述 求两个正整数 M 和 N 的最大公约数(M&#xff0c;N都在长整型范围内&#xff09; .输入 输入一行&#xff0c;包括两个正整数。 输出 输出只有一行&#xff0c;包括1个正整数。 样例 输入 45 60 输出 15 2.参考代码(C语言版) #include <stdio.h> …...

pytorch训练可视化工具---TensorBoard

一、目的&#xff1a;为什么使用 TensorBoard 调控模型 使用 TensorBoard 可以帮我们&#xff1a; 实时查看 loss / acc 曲线 → 判断是否过拟合、欠拟合&#xff1b; 对比不同模型或超参数的效果&#xff1b; 可视化模型结构 → 帮助调试模型设计&#xff1b; 查看权重/梯…...

丝杆升降机限位失灵深度剖析:从故障机理到智能监测方案

在工业自动化与精密机械传动领域&#xff0c;丝杆升降机凭借高精度、大推力的特性&#xff0c;成为产线设备的核心执行部件。然而&#xff0c;限位系统的可靠性直接决定设备安全运行与生产连续性。本文将从技术原理、故障诊断到智能监测方案&#xff0c;系统性解析丝杆升降机限…...

系统集成项目管理工程师学习笔记

第九章 项目管理概论 1、项目基本要素 项目基础 项目是为创造独特的产品、服务或成果而进行的临时性工作。 项目具有临时性、独特性、渐进明细的特点。项目的“临时性”是指项目只有明确的起点和终点。“临时性”并一定意味着项目的持续时间短。 项目可宣告结束的情况&…...

RDD的自定义分区器-案例

对电商订单数据进行处理&#xff0c;订单数据包含用户 ID 和订单金额&#xff0c;不同地区的用户有不同的 ID 范围。我们会按照地区对订单数据进行分区&#xff0c;这样做能让相同地区的订单数据处于同一分区&#xff0c;便于后续按地区进行统计金额分析。 订单数据如下&#x…...

牛客网NC231954:斐波那契数列 (简单的数列问题)

牛客网NC231954:斐波那契数列 (简单的数列问题&#xff09; 题目描述 本题要求我们计算斐波那契数列的第n项&#xff0c;斐波那契数列定义如下&#xff1a; f(1) 1f(2) 1f(n) f(n-1) f(n-2)&#xff0c;当n ≥ 3 给定整数n&#xff0c;求f(n)的值。 算法思路 斐波那契…...

中国近代史3

辛亥革命 1.同盟会&#xff1a;建立 1905年&#xff0c;东京&#xff0c;第一个全国性的资产阶级革命政党&#xff1b;同盟会纲领“驱除鞑虏&#xff0c;恢复中华&#xff0c;建立民国&#xff0c;平均地权” “民族”“民生”“民权” 2.武昌起义 ①爆发&#xff1a;1911.10…...

晶振的核心参数

目录 1.简介 2.晶振核心参数详解 3.晶振的抖动&#xff08;jitter&#xff09; 4.抖动的三种测量方式 5.抖动的其他资料 1.简介 再看一些晶振的手册时&#xff0c;经常遇到一些类似或相近的参数&#xff0c;今天借此机会&#xff0c;做一个小姐。 2.晶振核心参数详解 1…...

北京孙河傲云源墅:限量典藏的主城墅居臻品

在限墅令的背景下&#xff0c;北京主城的墅居产品日益稀缺&#xff0c;而傲云源墅作为孙河墅区的杰出之作&#xff0c;凭借其独特的价值&#xff0c;成为了众多高端置业者的理想选择。 傲云源墅所处的孙河地区&#xff0c;是北京公认的高价值板块。其地位在 2025 年孙河 2902 …...

驱动-Linux定时-timer_list

了解内核定时相关基础知识 文章目录 简要介绍timer_list 特点API 函数实验测试程序 - timer_mod.c编译文件-Makefile实验验证 注意事项总结 简要介绍 硬件为内核提供了一个系统定时器来计算流逝的时间&#xff08;即基于未来时间点的计时方式&#xff0c; 以当前时刻为计时开始…...

从理论到实战:模糊逻辑算法的深度解析与应用实践

从理论到实战&#xff1a;模糊逻辑算法的深度解析与应用实践 一、模糊逻辑的核心概念与数学基础 模糊逻辑&#xff08;Fuzzy Logic&#xff09;是一种处理不确定性的数学工具&#xff0c;其核心思想是将传统布尔逻辑的“非黑即白”扩展为连续的隶属度函数。例如&#xff0c;在…...

涨薪技术|0到1学会性能测试第65课-SQL捕获阻塞事件

前面的推文我们掌握了JVM调优技术。今天给大家分享MS SQL数据库监控与调优技术。后续文章都会系统分享干货&#xff0c;带大家从0到1学会性能测试。 01SQL捕获阻塞事件 在SQL Server 2005之前的版本&#xff0c;分析哪些进程产生阻塞以及哪些进程被阻塞&#xff0c;都需要使用脚…...

SQL实战:06交叉日期打折问题求解

文章目录 概述题目&#xff1a;交叉打折问题求解题解第一步&#xff1a;使用滑动窗口统计当前活动前的最大结束日期步骤二&#xff1a;拆分出交叉部分步骤三&#xff1a;计算每次活动的持续天数步骤四&#xff1a;分组统计最终结果完整SQL 概述 最近刷题时遇到一些比较有意思的…...

Linux云计算训练营笔记day09(MySQL数据库)

Linux云计算训练营笔记day09&#xff08;MySQL数据库&#xff09; 目录 Linux云计算训练营笔记day09&#xff08;MySQL数据库&#xff09;外键约束数据的导入和导出数据的导出数据的导入 DQL 数据查询语言查指定字段查所有字段where 过滤条件and 和 orin 和 not inbetween...an…...

docker 学习记录

docker pull nginx docker 将本地nginx快照保存到当前文件夹下 docker save -o nginx.tar nginx:latestdocker 将本地nginx 加载 docker load -i nginx.tar docker运行nginx在80端口 docker run --name dnginx -p 80:80 -d nginxredis启动 docker run --name mr -p 6379:6379 -…...

Kind方式部署k8s单节点集群并创建nginx服务对外访问

资源要求 请准备好doker环境&#xff0c;尽量用比较新的版本。我的docker环境如下 docker 环境&#xff1a; Docker version 20.10.21, build 20.10.21-0ubuntu1~18.04.3 安装kind kind表现上就是一个二进制程序&#xff0c;下载对应版本并增加执行权限即可&#xff1a; cu…...

Da14531蓝牙特征值1读没有回调解决

一. 我们调试中发现user_peripheral.c中的回调&#xff0c;一直都没有回调。&#xff08;大家可以通过打印去排查&#xff09; void user_catch_rest_hndl(ke_msg_id_t const msgid, void const *param, ke_task_id_t const dest_id, ke_task_id_t const src_id) { //此处省…...

journal of Electronic Imaging(JEI)投稿咨询

研究生投的第二篇论文-CV方向&#xff0c;由于太菜了&#xff0c;到处被拒&#xff0c;最后选择了Journal of Electronic Imaging(JEI) 审稿了三个月&#xff0c;最近突然变了状态&#xff0c;之前催稿说才一个审稿人&#xff0c;这样子是不是要被拒了&#xff0c;有没有知道的…...

upload-labs靶场通关详解:第6-9关

目录 第六关&#xff1a;大小写绕过 一、分析源代码 二、解题思路 三、解题步骤 第七关&#xff1a;空格绕过 一、分析源代码 二、解题思路 三、解题步骤 第八关&#xff1a;点号绕过 一、分析源代码 二、解题思路 三、解题步骤 第九关&#xff1a;::$DATA字符串绕…...

算法图表总结:查找、排序与递归(含 Mermaid 图示)

算法图表总结&#xff1a;查找、排序与递归&#xff08;含 Mermaid 图示&#xff09; 分类标签&#xff1a;算法、数据结构、Mermaid、技术图表 关键词&#xff1a; 算法可视化、Mermaid 图表、数据结构、二分查找、快速排序、递归树 摘要&#xff1a; 本文通过 Mermaid 图表…...

在文件检索方面doris和elasticsearch的区别

apache Doris 与 Elasticsearch 在文件检索领域的差异源于技术架构与定位目标的本质区别,以下从核心维度对比分析二者的技术特性: 一、 ‌架构设计与定位差异‌ ‌维度‌‌Apache Doris‌‌Elasticsearch‌‌核心架构‌分布式 MPP 列式分析引擎,面向 OLAP 优化分布式倒排索…...

linux系统服务

Linux 系统服务&#xff08;System Services&#xff09; 是在后台持续运行的进程&#xff08;守护进程&#xff0c;即 daemon&#xff09;&#xff0c;用于提供核心功能或支持其他应用程序&#xff08;如网络管理、日志记录、定时任务等&#xff09;。它们通常在系统启动时自动…...

大语言模型三大演进方向:记忆增强、工具集成与多模态突破

目录 一、方向演进:从通用模型到记忆增强系统 1.1 技术瓶颈分析 1.2 记忆增强技术路径 1.3 企业级应用架构 二、工具调用:从语言理解到行动执行 2.1 工具调用协议演进 2.2 工具编排范式比较 三、多模态突破:跨模态统一建模 3.1 多模态架构演进 3.2 医学多模态应用…...

嵌入式学习笔记DAY21(双向链表、Makefile)

一、双向链表 1.概念 双向链表&#xff08;Doubly Linked List&#xff09; 是一种链式数据结构&#xff0c;每个节点包含 两个指针&#xff08;前驱指针 prev 和后继指针 next&#xff09;&#xff0c;分别指向 前一个节点 和 后一个节点&#xff0c;形成双向连接。 头节点&…...

Vue 学习随笔系列二十三 -- el-date-picker 组件

el-date-picker 组件 文章目录 el-date-picker 组件el-date-picker 只有某些日期可选 el-date-picker 只有某些日期可选 <template><div><el-form ref"form" size"mini":model"form" :rules"rules"label-width"8…...

IEEE出版|连续多年稳定检索|第三届信号处理与智能计算国际学术会议(SPIC2025)

【重要信息】 会议官网&#xff1a; www.ic-spic.com 会议日期&#xff1a;2025年11月28-30日 会议地点&#xff1a;中国 广州 截稿日期&#xff1a;2025年11月10日 接受或拒绝通知日期&#xff1a;提交后7个工作日 【征稿主题】 人工智能和机器学习 计算机系统和架构 …...

用Python代码绘制动态3D爱心效果

引言 介绍Python在创意编程中的应用&#xff0c;特别是如何通过简单的代码实现视觉上的美感。引出本文将分享的爱心代码&#xff0c;并简要说明其实现原理。 爱心代码的基本实现 展示一个简单的Python代码示例&#xff0c;使用字符画的方式在控制台中绘制一个爱心图案。 pr…...

牛客网刷题:NC208813求逆序数

牛客网刷题&#xff1a;NC208813求逆序数 问题描述 在排序和数据结构分析中&#xff0c;逆序数是一个重要的概念。对于一个数列来说&#xff0c;如果一对数的前后位置与大小顺序相反&#xff08;即前面的数大于后面的数&#xff09;&#xff0c;那么它们就称为一个逆序对。一个…...

Day 21 训练

Day 21 训练 常见的降维算法数据预处理无监督降维PCA&#xff08;主成分分析&#xff09;主成分分析&#xff08;PCA&#xff09;作用和优势应用场景t-SNE&#xff08;t-分布随机邻域嵌入&#xff09;t-SNE&#xff08;t-分布随机邻域嵌入&#xff09;为什么 t-SNE 特别适用于高…...

1267, “Illegal mix of collations (latin1_swedish_ci,IMPLICIT

python 执行数据迁移报错 mysql : 1267, "Illegal mix of collations (latin1_swedish_ci,IMPLICIT 解决方法&#xff1a; 替换TABLE 后面的表名为你自己的表名&#xff0c;mysql 黑窗口执行。 以下是我的表名&#xff0c;仅作参考 ALTER TABLE book CONVERT TO CHARACTE…...

【C#】Thread.Join()、异步等待和直接join

JogThread.Join() 是 .NET 中 System.Threading.Thread 类的一个方法&#xff0c;用来让当前调用线程暂停执行&#xff0c;直到目标线程&#xff08;这里是 JogThread&#xff09;终止为止。以下是它的核心语义和你在 UI 代码里需要注意的几个相关知识点。 1. Thread.Join() 的…...

Malformed input or input contains unmappable characters解决

JDK 17 文件上传编码异常解决方案技术文档 1. 问题背景 在 JDK 17 环境下&#xff0c;文件上传过程中可能抛出 Malformed input or input contains unmappable characters 错误。此问题通常由以下原因触发&#xff1a; 文件路径/名称包含非 ASCII 字符&#xff08;如中文、日…...

PYTHON训练营DAY26

一、函数 &#xff08;一&#xff09;不带参数的函数 # 定义一个简单的问候函数 def greet():"""打印一句问候语。"""message "大家好&#xff01;欢迎学习Python函数定义&#xff01;"print(message)greet()&#xff08;二&#x…...

奇变偶不变,符号看象限

三角函数诱导公式口诀详解&#xff1a;奇变偶不变&#xff0c;符号看象限 口诀解析 1. 口诀含义 奇变偶不变&#xff1a; 奇/偶&#xff1a;指角度加减的是π/2&#xff08;90&#xff09;的奇数倍还是偶数倍 奇数倍&#xff08;如π/2, 3π/2&#xff09;→ 函数名改变&…...

基于SpringBoot的家政服务系统设计与实现(源码+文档+部署讲解)

技术范围&#xff1a;SpringBoot、Vue、SSM、HLMT、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app、大数据、物联网、机器学习等设计与开发。 主要内容&#xff1a;免费功能设计、开题报告、任务书、中期检查PPT、系统功能实现、代码编写、论文编写和辅导、论文…...

Makefile 在 Go 项目中的实践

在 Go 项目中&#xff0c;Makefile 是一个强大的工具&#xff0c;用于自动化构建、测试和部署流程。它不仅能减少重复命令输入&#xff0c;还能确保团队开发环境的一致性。本文以 CoreDNS&#xff08;一个高性能 DNS 服务器&#xff09;的 Makefile 为例&#xff0c;解析其设计…...

关闭所有Nginx进程

要关闭所有Nginx进程&#xff0c;可以使用以下命令。这些命令适用于不同的操作系统。 在Linux/Unix系统中 在Linux或Unix系统中&#xff0c;可以使用killall命令来关闭所有Nginx进程。 sudo killall nginx 在Windows系统中 在Windows系统中&#xff0c;可以使用taskkill命…...

开源模型应用落地-模型上下文协议(MCP)-Resources-资源的使用逻辑

一、前言 在大型语言模型与外部世界交互的探索中&#xff0c;如何高效、灵活地接入多样化数据始终是核心命题。MCP&#xff08;Model Context Protocol&#xff09;协议中的Resources 机制&#xff0c;正是为这一问题提供了优雅的解决方案。通过URI&#xff08;统一资源标识符&…...

如何判断一个网站后端是用什么语言写的

判断一个网站的后端是用什么语言写的&#xff0c;可以从以下几个方面入手&#xff1a; 一、通过响应头&#xff08;HTTP Response Headers&#xff09; 使用浏览器开发者工具或工具如 curl 查看网站返回的响应头信息&#xff0c;有时可以看到蛛丝马迹&#xff1a; 示例&#…...

CertiK助力以太坊扩展战略,解析Pectra升级的变革与挑战

近期&#xff0c;美国知名金融科技媒体Benzinga发表文章&#xff0c;深入探讨以太坊Pectra升级的变革性影响&#xff0c;并特别引用了CertiK对潜在风险的权威分析&#xff0c;特别是EIP-7702引入的全新信任模型变化。此次升级不仅重新定义了EOA与智能合约的交互方式&#xff0c…...

【C++】Module CPP:模块化编程 Demo

一、C20 模块简介 C20 模块是 C 语言发展史上的重要革新&#xff0c;它从根本上改变了代码组织方式。相比传统的头文件&#xff08;#include&#xff09;机制&#xff0c;模块具有以下核心优势&#xff1a; 隔离编译&#xff1a;模块独立编译&#xff0c;避免重复编译头文件符…...