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

动态规划18:188. 买卖股票的最佳时机 IV

动态规划解题步骤:

1.确定状态表示:dp[i]是什么

2.确定状态转移方程:dp[i]等于什么

3.初始化:确保状态转移方程不越界

4.确定填表顺序:根据状态转移方程即可确定填表顺序

5.确定返回值

题目链接:188. 买卖股票的最佳时机 IV - 力扣(LeetCode)

题解:

本题与动态规划17:123. 买卖股票的最佳时机 III 几乎无异

1.状态表示:

f[k][i]表示截止第i天,第i天为可买入状态的最大利润,且当前已交易k次

g[k][i]表示截止第i天,第i天为可卖出状态的最大利润,且当前已交易k次

2.状态转移方程:

f[k][i]=max(f[k][i-1],g[k-1][i-1]+prices[i])

g[k][i]=max(g[k][i-1],f[k][i-1]-prices[i])

3.初始化:初始化第一列为负无穷(-0x3f3f3f3f),另外 f[0][0]=0   g[0][0]=-prices[0];

注意:对于f表,其本应该初始化第一行和第一列,但是为了优化代码和g表保持一致,可以只初始化第一列,对于第一行的数据只需对其状态转移方程添加位置判断即可,对于不合法的位置其状态转移方程为f[k][i-1],合法位置的状态转移方程为max(f[k][i-1],g[k-1][i-1]+prices[i])

4.填表顺序:从上往下,从左往右,两个表一起填

5.返回值:返回第n-1天为可买入状态的最大利润(交易次数可能为0、1、2......K)所以需要遍历第n-1列

class Solution {
public:int maxProfit(int K, vector<int>& prices) {const int INF=0x3f3f3f3f;//f[k][i]表示截止第i天,第i天为可买入状态的最大利润,且当前已交易k次//g[k][i]表示截止第i天,第i天为可卖出状态的最大利润,且当前已交易k次//第i天为可买入状态,则前一天有两种情况:前一天为可买入状态,交易次数相同,今天什么也没做;//                                   前一天为可卖出状态,交易次数少1,今天卖出了股票//f[k][i]=max(f[k][i-1],g[k-1][i-1]+prices[i])//第i天为可卖出状态,则前一天有两种情况:前一天为可卖出状态,交易次数相同,今天什么也没做//                                   前一天为可买入状态,交易次数相同,今天买了股票//g[k][i]=max(g[k][i-1],f[k][i-1]-prices[i])size_t n=prices.size();//处理边界条件if(n==1) return 0;//创建dp表vector<vector<int>> f(K+1,vector<int>(n,-INF));vector<vector<int>> g(K+1,vector<int>(n,-INF));//初始化(创建dp表时已初始化一部分,相当于初始化了第一列)f[0][0]=0;g[0][0]=-prices[0];//填表for(int k=0;k<=K;++k){for(int i=1;i<n;++i){if(k-1>=0) f[k][i]=max(f[k][i-1],g[k-1][i-1]+prices[i]);else f[k][i]=f[k][i-1];g[k][i]=max(g[k][i-1],f[k][i-1]-prices[i]);}}//返回值int ans=INT_MIN;for(int k=0;k<=K;++k)if(f[k][n-1]>ans) ans=f[k][n-1];return ans;}
};

相关文章:

动态规划18:188. 买卖股票的最佳时机 IV

动态规划解题步骤&#xff1a; 1.确定状态表示&#xff1a;dp[i]是什么 2.确定状态转移方程&#xff1a;dp[i]等于什么 3.初始化&#xff1a;确保状态转移方程不越界 4.确定填表顺序&#xff1a;根据状态转移方程即可确定填表顺序 5.确定返回值 题目链接&#xff1a;188.…...

YOLOv8改进 - 注意力篇 - 引入ShuffleAttention注意力机制

一、本文介绍 作为入门性篇章&#xff0c;这里介绍了ShuffleAttention注意力在YOLOv8中的使用。包含ShuffleAttention原理分析&#xff0c;ShuffleAttention的代码、ShuffleAttention的使用方法、以及添加以后的yaml文件及运行记录。 二、ShuffleAttention原理分析 ShuffleA…...

基于Multisim的8路彩灯循环控制电路设计与仿真

1)由八个彩灯LED的明暗构成各种彩灯图形; 2)彩灯依次显示的图形: 彩灯从左至右渐亮至全亮(8个CP) 彩灯从左至右渐灭至全灭(8个CP) 彩灯从右至左渐亮至全亮(8个CP) 彩灯从右至左渐灭至全灭(8个CP) 彩灯全亮(1个CP) 彩灯全灭(1个CP) 彩灯全亮(1个CP) 彩灯全灭(1个CP) 3)彩灯图形循…...

完整的模型训练套路 pytorch

**前置知识&#xff1a; 1、 &#xff08;1&#xff09;.train()&#xff1a;将模型设置为训练模式 &#xff08;2&#xff09;.eval()&#xff1a;将模型设置为评估模式 不写也可以&#xff08;只对特定网络模型有作用&#xff0c;如含有Dropout的&#xff09; 2、 with…...

2024年十大前沿图像分割模型汇总:工作机制、优点和缺点介绍

《博主简介》 小伙伴们好&#xff0c;我是阿旭。专注于人工智能、AIGC、python、计算机视觉相关分享研究。 ✌更多学习资源&#xff0c;可关注公-仲-hao:【阿旭算法与机器学习】&#xff0c;共同学习交流~ &#x1f44d;感谢小伙伴们点赞、关注&#xff01; 《------往期经典推…...

Notepad++将搜索内容所在行选中,并进行复制等操作

背景 Notepad在非常多的数据行内容中&#xff0c;按照指定内容检索&#xff0c;并定位到具体行&#xff0c;而后对内容行的数据进行复制、剪切、删除等处理动作。 操作说明 检索并标记所在行 弹出搜索框&#xff1a;按下 Ctrl F。 输入查找字符串&#xff1a;在搜索框中输入要…...

[Java EE] IP 协议 | NAT 机制 | 路由选择 | MAC 地址 | 域名解析服务

Author&#xff1a;MTingle major:人工智能 Build your hopes like a tower! 目录 一. 初识 IP 协议 IP 协议报头: 二. IP 协议如何管理地址 NAT机制 路由选择 三. 数据链路层(以太网): MAC地址 四. 域名解析系统 一. 初识 IP 协议 IP 协议工作在网络层,其目标是为了在复…...

赋能特大城市水务数据安全高速运算,深圳计算科学研究院YashanDB数据库系统斩获“鼎新杯”二等奖

第三届“鼎新杯”数字化转型应用优秀案例评选结果日前正式公布&#xff0c;深圳计算科学研究院联合深圳市环境水务集团有限公司申报的《深圳环境水务国产数据库YashanDB&#xff0c;赋能特大城市水务数据安全高速运转》案例&#xff0c;经过5个多月的评审&#xff0c;从4000申报…...

RAYDATA链接PGSQL做图表

1.拖一个脚本进去 2.拖一个柱状图进去 3.双击脚本写代码 using System; using System.Collections; using System.Collections.Generic; using System.Linq; using Ventuz.Kernel; using Npgsql; using System.Threading; using System.Threading.Tasks;public class Script…...

UE5里的TObjectPtr TSharedPtr TWeakPtr有什么区别

在 Unreal Engine&#xff08;UE&#xff09;编程中&#xff0c;TObjectPtr、TSharedPtr 和 TWeakPtr 都是 指针类型&#xff0c;但它们在生命周期管理和使用场景上有不同的特点。让我们详细分析这些指针的区别和用途。 TObjectPtr TObjectPtr 是 UE5 中引入的新智能指针类型…...

前端--深入理解HTTP协议

HTTP 协议简介 HTTP&#xff08;HyperText Transfer Protocol&#xff0c;超文本传输协议&#xff09;是一个应用层协议&#xff0c;用于在客户端&#xff08;通常是浏览器&#xff09;和服务器之间传输超文本数据&#xff08;如 HTML、CSS、JavaScript 等&#xff09;。它是万…...

线性代数 向量

一、定义 几何定义&#xff1a;向量是一个有方向和大小的量&#xff0c;通常用箭头表示。向量的起点称为原点&#xff0c;终点称为向量的端点。 代数定义&#xff1a;向量是一个有序的数组&#xff0c;通常表示为列向量或行向量。 行向量就是 1*n的形式&#xff08;行展开&…...

go中阶乘实现时递归及迭代方式的比较

package mainimport ("fmt""time""math/big" )// 使用递归和 big.Int 计算阶乘 func FactorialRecursive(n *big.Int) *big.Int {if n.Cmp(big.NewInt(0)) 0 {return big.NewInt(1)}return new(big.Int).Mul(n, FactorialRecursive(new(big.Int…...

Jupyter notebook中更改字体大小

文章目录 方法一&#xff1a;局部修改方法二&#xff1a;全局修改 Jupyter notebook提供了一个非常方便的跨平台交互代码编译环境&#xff0c;但是单元格的内的代码字体往往显示较小&#xff0c;不利于观看。本人查了很多方法来调整字体&#xff0c;后来发现既不需要更改jupyte…...

关于Ubuntu服务器的时间同步设置以及Linux什么时候开始使用swap虚拟内存

一、关于Ubuntu服务器的时间同步设置 首先我们检查一下服务器的时区设置和当前时间值&#xff0c;获取/etc/timezone 配置以及使用date命令查看当前时间。 rootiZ2ze7n2ynw18p6bs92fziZ:~# cat /etc/timezone Asia/Shanghai rootiZ2ze7n2ynw18p6bs92fziZ:~# date Wed Dec 21 …...

Java Stream API 详解

Java Stream API 详解 1. 什么是 Stream API&#xff1f; Stream API 是 Java 8 引入的一种用于处理集合&#xff08;如数组、列表&#xff09;的强大工具。它提供了一种声明性方式处理数据&#xff0c;可以简化代码并提高可读性。Stream 不是数据结构&#xff0c;它只是一种…...

一文了解大模型中的SDK和API

大白话聊SDK和API-知乎 1.智谱AI的SDK和API 以智谱AI为例&#xff0c;智谱AI的SDK是名为zhipuai的Python包&#xff0c;其中包含了用于访问API的接口&#xff08;如api-key&#xff09;。在这个框架中&#xff0c;API是SDK的一部分&#xff0c;用于实现与智谱AI服务的交互。 …...

element plus的el-select分页

摘要&#xff1a; el-select的数据比较多的时候&#xff0c;必须要分页&#xff0c;处理方案有全部数据回来&#xff0c;或者添加搜索功能&#xff0c;但是就有个问题就是编辑的时候回显问题&#xff0c;必须要保证select的数据有对应的id与name匹配回显&#xff01; <el-fo…...

STM32CubeMX【串口收发USART】

第一步&#xff0c;配置cubemx 配置好点右上角生成 第二步&#xff0c;串口方式 阻塞式发送 英文、中文正常、浮点有口 /* Initialize all configured peripherals */MX_GPIO_Init();MX_USART1_UART_Init();//配置完自动生成的 发送到串口助手上 while (1){/* USER CODE…...

【学术会议投稿】Java Web开发实战:从零到一构建动态网站

【会后3-4个月检索|IEEE出版】第五届人工智能与计算机工程国际学术会议&#xff08;ICAICE 2024&#xff09;_艾思科蓝_学术一站式服务平台 更多学术会议请看&#xff1a; https://ais.cn/u/nuyAF3 目录 引言 一、Java Web开发基础 1. Java Web开发简介 2. 开发环境搭建 …...

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

华为云AI开发平台ModelArts

华为云ModelArts&#xff1a;重塑AI开发流程的“智能引擎”与“创新加速器”&#xff01; 在人工智能浪潮席卷全球的2025年&#xff0c;企业拥抱AI的意愿空前高涨&#xff0c;但技术门槛高、流程复杂、资源投入巨大的现实&#xff0c;却让许多创新构想止步于实验室。数据科学家…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

Android15默认授权浮窗权限

我们经常有那种需求&#xff0c;客户需要定制的apk集成在ROM中&#xff0c;并且默认授予其【显示在其他应用的上层】权限&#xff0c;也就是我们常说的浮窗权限&#xff0c;那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...