动态规划——买卖股票的最佳时机含冷冻期

1、题目链接

leetcode 309. 买卖股票的最佳时机含冷冻期

 2、题目分析

该题有我们可以定义三种状态,买入状态,可交易状态 ,冷冻期状态

我们可以建立一个n*3的二维数组来表示这三种状态:

根据这个图可以看出,

可以从买入状态卖出变成可交易状态,或者从买入状态还是到买入状态(什么也不干),

可以从可交易状态到买入状态,或者从可交易状态到可交易状态(什么也不干)

可以从冷冻期状态到可交易状态(只有这一种情况)

根据以上信息,可以列出状态转移方程:

dp[i][0]表示在第i天,处于买入状态时所获得的最大利润

dp[i][1]表示在第i天,处于可交易状态时所获得的最大利润

dp[i][2]表示在第i天,处于冷冻期状态时所获得的最大利润

那么:

dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i]);

dp[i][1]=max(dp[i-1][1],dp[i-1][2]);

dp[i][2]=dp[i-1][0]+prices[i];

 3、代码解析

int maxProfit(vector<int>& prices) {int n=prices.size();vector<vector<int>>dp(n,vector<int>(3));//dp[i][0]表示在第i天,处于买入状态时所获得的最大利润//dp[i][1]表示在第i天,处于可交易状态时所获得的最大利润//dp[i][2]表示在第i天,处于冷冻期状态时所获得的最大利润//初始化dp[0][0]=-prices[0];dp[0][1]=0;dp[0][2]=0;for(int i=1;i<n;i++){dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i]);dp[i][1]=max(dp[i-1][1],dp[i-1][2]);dp[i][2]=dp[i-1][0]+prices[i];}return max(dp[n-1][1],dp[n-1][2]);}

完结!

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

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

相关文章

探索Linux的奇妙世界:第二关---Linux的基本指令1

1. xshell与服务器的连接 想必大家在看过上一期视频时已经搭建好了Linux的环境了并且已经下好了终端---xshell了吧?让我来带大家看一看下好了是什么样子的: 第一次登陆会让你连接你的服务器,就是我们买的云服务器,买完之后需要把公网地址ip复制过来进行链接,需要用户名和密码连…

【从0实现React18】 (一) 项目初始化

Multi-repo 和 Mono-repo 由于需要同时管理多个包&#xff0c;如React、React-dom等&#xff0c;所以选择**Mono-repo** 选择使用pnpm-workspace搭建Mono-repo环境的原因 依赖安装快更规范 Pnpm初始化 npm install -g pnpm pnpm init配置pnpm-workspace.yml文件 pnpm-work…

【单片机毕业设计选题24020】-全自动鱼缸的设计与应用

系统功能: &#xff08;1&#xff09;检测并控制鱼缸水温&#xff0c;水温低于22℃后开启加热&#xff0c;高于28℃后关闭加热。 &#xff08;2&#xff09;定时喂食&#xff0c;每天12点和0点喂食一次&#xff0c;步进电机开启后再关闭模拟喂食。 &#xff08;3&#xff09…

1950 Springboot汽修技能点评系统idea开发mysql数据库APP应用java编程计算机网页源码maven项目

一、源码特点 springboot 汽修技能点评系统是一套完善的信息系统&#xff0c;结合springboot框架和bootstrap完成本系统&#xff0c;对理解JSP java编程开发语言有帮助系统采用springboot框架&#xff08;MVC模式开发&#xff09;&#xff0c;系统 具有完整的源代码和数据库&…

TOPGP-TIPTOP调用外部Webservice

功能要求&#xff1a;ERP作业调用外部系统的webserice更新数据。 演示环境&#xff1a;ERP作业cooi002&#xff08;员工档案&#xff09;录入后更新到外部系统员工档案表。 1、外部系统的WebSerice使用.net搭建 2、在Service.cs中写一个调用方法erp_other erp_other中两个参数…

【实战】Spring Cloud Stream 3.1+整合Kafka

文章目录 前言新版版本优势实战演示增加maven依赖增加applicaiton.yaml配置新增Kafka通道消费者新增发送消息的接口 实战测试postman发送一个正常的消息postman发送异常消息 前言 之前我们已经整合过Spring Cloud Stream 3.0版本与Kafka、RabbitMQ中间件&#xff0c;简直不要太…

推荐4款电脑软件,简单已入手,关键是免费,建议收藏

拖把更名器 拖把更名器是一款功能强大的文件名称修改工具&#xff0c;主要用于批量进行文件更名和整理音乐文件标签。该软件结合资源管理器右键菜单&#xff0c;支持多种文件格式和操作方式&#xff0c;包括MP3、RM、RMVB、WMA等标签更名&#xff0c;文件名、标签内码转换、繁简…

【SpringSecurity】认证与鉴权框架SpringSecurity——认证

目录 SpringSecurity介绍特性CSRF攻击攻击模式攻击原理预防手段 XSS攻击攻击模式危害预防手段 SpringSecurity预防CSRF攻击SpringSecurity预防XSS攻击SpringSecurity与OAuth2的关系SpringSecurity的核心功能 代码实战依赖定义一个接口Redis工具类响应类直接运行工具类认证业务密…

VERYCLOUD睿鸿股份亮相亚马逊云科技中国峰会2024

5月30日&#xff0c;为期两天的亚马逊云科技中国峰会在上海世博中心圆满落幕。 多位大咖现场分享&#xff0c;生成式AI时代的数据战略&#xff0c;企业级AI应用&#xff0c;最新技术、产品重磅发布&#xff0c;创新行业解决方案 …… 作为亚马逊云科技的生态合作伙伴&#x…

Android面试题:App性能优化之Java和Kotlin常见的数据结构

本文首发于公众号“AntDream”&#xff0c;欢迎微信搜索“AntDream”或扫描文章底部二维码关注&#xff0c;和我一起每天进步一点点 Java常见数据结构特点 ArrayList ArrayList底层是基于数组实现add、删除元素需要进行元素位移耗性能&#xff0c;但查找和修改块适合不需要频…

GPT-4o的视觉识别能力,将绕过所有登陆的图形验证码

知识星球&#x1f517;除了包含技术干货&#xff1a;《Java代码审计》《Web安全》《应急响应》《护网资料库》《网安面试指南》还包含了安全中常见的售前护网案例、售前方案、ppt等&#xff0c;同时也有面向学生的网络安全面试、护网面试等。 我们来看一下市面上常见的图形验证…

状态压缩DP——AcWing 291. 蒙德里安的梦想

状态压缩DP 定义 状态压缩DP是一种利用二进制数来表示状态的动态规划算法。它通过将状态压缩成一个整数&#xff0c;从而减少状态数量&#xff0c;提高算法效率。 运用情况 状态压缩DP通常用于解决具有状态转移和最优解性质的问题&#xff0c;例如组合优化、图论、游戏等问…

Vue82-组件内路由守卫

一、组件内路由守卫的定义 在一个组件里面去写路由守卫&#xff0c;而不是在路由配置文件index.js中去写。 此时&#xff0c;该路由守卫是改组件所独有的&#xff01; 只有通过路由规则进入的方式&#xff0c;才会调这两个函数&#xff0c;否则&#xff0c;若是只是用<Ab…

LogicFlow 学习笔记——9. LogicFlow 进阶 节点

LogicFlow 进阶 节点&#xff08;Node&#xff09; 连线规则 在某些时候&#xff0c;我们可能需要控制边的连接方式&#xff0c;比如开始节点不能被其他节点连接、结束节点不能连接其他节点、用户节点后面必须是判断节点等&#xff0c;想要达到这种效果&#xff0c;我们需要为…

【经验分享】RT600 serial boot mode测试

【经验分享】RT600 serial boot mode测试 一&#xff0c; 文档描述二&#xff0c; Serial boot mode测试2.1 evkmimxrt685_gpio_led_output 工程测试2.2 evkmimxrt685_dsp_hello_world_usart_cm33工程测试 一&#xff0c; 文档描述 RT600的启动模式共支持4种&#xff1a; 1&am…

C++设计模式——Composite组合模式

一&#xff0c;组合模式简介 真实世界中&#xff0c;像企业组织、文档、图形软件界面等案例&#xff0c;它们在结构上都是分层次的。将系统分层次的方式使得统一管理和添加不同子模块变得容易&#xff0c;在软件开发中&#xff0c;组合模式的设计思想和它们类似。 组合模式是…

数据库设计概述-数据库设计内容、数据库设计方法(基于E-R模型的规范设计方法)

一、引言 如何利用关系数据库理论设计一个满足应用系统需求的数据库 二、数据库设计内容 1、数据库设计是基于应用系统需求分析中对数据的需求&#xff0c;解决数据的抽象、数据的表达和数据的存储结构等问题 2、其目标是设计出一个满足应用要求、简洁、高效、规范合理的数…

Redis 集群 - 数据分片算法

前言 广义的集群&#xff1a;只要是多个机器构成了一个分布式系统&#xff0c;都可以被称为集群。 狭义的集群&#xff1a;redis 的集群模式&#xff0c;这个集群模式下&#xff0c;主要是解决存储空间不足的问题。 Redis 集群 redis 采用主从结构&#xff0c;可以提高系统的可…

「动态规划」如何求最长湍流子数组的长度?

78. 最长湍流子数组https://leetcode.cn/problems/longest-turbulent-subarray/description/ 给定一个整数数组arr&#xff0c;返回arr的最长湍流子数组的长度。如果比较符号在子数组中的每个相邻元素对之间翻转&#xff0c;则该子数组是湍流子数组。更正式地来说&#xff0c;…

从开源EPR产品Odoo学习

前言 一个先进、敏捷、经济高效、可快速扩展的Odoo免费开源企业信息化解决方案&#xff0c;让企业获得适应未来发展的长期创新和增长能力。 Odoo 的免费开源模式 让我们可利用无数开发人员和业务专家&#xff0c;在短短数年内&#xff0c;打造数百款应用。凭借强大的技术基础&…