动态规划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
动态规划解题步骤: 1.确定状态表示:dp[i]是什么 2.确定状态转移方程:dp[i]等于什么 3.初始化:确保状态转移方程不越界 4.确定填表顺序:根据状态转移方程即可确定填表顺序 5.确定返回值 题目链接:188.…...
YOLOv8改进 - 注意力篇 - 引入ShuffleAttention注意力机制
一、本文介绍 作为入门性篇章,这里介绍了ShuffleAttention注意力在YOLOv8中的使用。包含ShuffleAttention原理分析,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
**前置知识: 1、 (1).train():将模型设置为训练模式 (2).eval():将模型设置为评估模式 不写也可以(只对特定网络模型有作用,如含有Dropout的) 2、 with…...
2024年十大前沿图像分割模型汇总:工作机制、优点和缺点介绍
《博主简介》 小伙伴们好,我是阿旭。专注于人工智能、AIGC、python、计算机视觉相关分享研究。 ✌更多学习资源,可关注公-仲-hao:【阿旭算法与机器学习】,共同学习交流~ 👍感谢小伙伴们点赞、关注! 《------往期经典推…...
Notepad++将搜索内容所在行选中,并进行复制等操作
背景 Notepad在非常多的数据行内容中,按照指定内容检索,并定位到具体行,而后对内容行的数据进行复制、剪切、删除等处理动作。 操作说明 检索并标记所在行 弹出搜索框:按下 Ctrl F。 输入查找字符串:在搜索框中输入要…...
[Java EE] IP 协议 | NAT 机制 | 路由选择 | MAC 地址 | 域名解析服务
Author:MTingle major:人工智能 Build your hopes like a tower! 目录 一. 初识 IP 协议 IP 协议报头: 二. IP 协议如何管理地址 NAT机制 路由选择 三. 数据链路层(以太网): MAC地址 四. 域名解析系统 一. 初识 IP 协议 IP 协议工作在网络层,其目标是为了在复…...
赋能特大城市水务数据安全高速运算,深圳计算科学研究院YashanDB数据库系统斩获“鼎新杯”二等奖
第三届“鼎新杯”数字化转型应用优秀案例评选结果日前正式公布,深圳计算科学研究院联合深圳市环境水务集团有限公司申报的《深圳环境水务国产数据库YashanDB,赋能特大城市水务数据安全高速运转》案例,经过5个多月的评审,从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(UE)编程中,TObjectPtr、TSharedPtr 和 TWeakPtr 都是 指针类型,但它们在生命周期管理和使用场景上有不同的特点。让我们详细分析这些指针的区别和用途。 TObjectPtr TObjectPtr 是 UE5 中引入的新智能指针类型…...
前端--深入理解HTTP协议
HTTP 协议简介 HTTP(HyperText Transfer Protocol,超文本传输协议)是一个应用层协议,用于在客户端(通常是浏览器)和服务器之间传输超文本数据(如 HTML、CSS、JavaScript 等)。它是万…...
线性代数 向量
一、定义 几何定义:向量是一个有方向和大小的量,通常用箭头表示。向量的起点称为原点,终点称为向量的端点。 代数定义:向量是一个有序的数组,通常表示为列向量或行向量。 行向量就是 1*n的形式(行展开&…...
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中更改字体大小
文章目录 方法一:局部修改方法二:全局修改 Jupyter notebook提供了一个非常方便的跨平台交互代码编译环境,但是单元格的内的代码字体往往显示较小,不利于观看。本人查了很多方法来调整字体,后来发现既不需要更改jupyte…...
关于Ubuntu服务器的时间同步设置以及Linux什么时候开始使用swap虚拟内存
一、关于Ubuntu服务器的时间同步设置 首先我们检查一下服务器的时区设置和当前时间值,获取/etc/timezone 配置以及使用date命令查看当前时间。 rootiZ2ze7n2ynw18p6bs92fziZ:~# cat /etc/timezone Asia/Shanghai rootiZ2ze7n2ynw18p6bs92fziZ:~# date Wed Dec 21 …...
Java Stream API 详解
Java Stream API 详解 1. 什么是 Stream API? Stream API 是 Java 8 引入的一种用于处理集合(如数组、列表)的强大工具。它提供了一种声明性方式处理数据,可以简化代码并提高可读性。Stream 不是数据结构,它只是一种…...
一文了解大模型中的SDK和API
大白话聊SDK和API-知乎 1.智谱AI的SDK和API 以智谱AI为例,智谱AI的SDK是名为zhipuai的Python包,其中包含了用于访问API的接口(如api-key)。在这个框架中,API是SDK的一部分,用于实现与智谱AI服务的交互。 …...
element plus的el-select分页
摘要: el-select的数据比较多的时候,必须要分页,处理方案有全部数据回来,或者添加搜索功能,但是就有个问题就是编辑的时候回显问题,必须要保证select的数据有对应的id与name匹配回显! <el-fo…...
STM32CubeMX【串口收发USART】
第一步,配置cubemx 配置好点右上角生成 第二步,串口方式 阻塞式发送 英文、中文正常、浮点有口 /* Initialize all configured peripherals */MX_GPIO_Init();MX_USART1_UART_Init();//配置完自动生成的 发送到串口助手上 while (1){/* USER CODE…...
【学术会议投稿】Java Web开发实战:从零到一构建动态网站
【会后3-4个月检索|IEEE出版】第五届人工智能与计算机工程国际学术会议(ICAICE 2024)_艾思科蓝_学术一站式服务平台 更多学术会议请看: https://ais.cn/u/nuyAF3 目录 引言 一、Java Web开发基础 1. Java Web开发简介 2. 开发环境搭建 …...
C++实现分布式网络通信框架RPC(3)--rpc调用端
目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中,我们已经大致实现了rpc服务端的各项功能代…...
简易版抽奖活动的设计技术方案
1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...
微信小程序 - 手机震动
一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注:文档 https://developers.weixin.qq…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...
Spring AI 入门:Java 开发者的生成式 AI 实践之路
一、Spring AI 简介 在人工智能技术快速迭代的今天,Spring AI 作为 Spring 生态系统的新生力量,正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务(如 OpenAI、Anthropic)的无缝对接&…...
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 的密码…...
QT3D学习笔记——圆台、圆锥
类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体(对象或容器)QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质(定义颜色、反光等)QFirstPersonC…...
08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险
C#入门系列【类的基本概念】:开启编程世界的奇妙冒险 嘿,各位编程小白探险家!欢迎来到 C# 的奇幻大陆!今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类!别害怕,跟着我,保准让你轻松搞…...
实战三:开发网页端界面完成黑白视频转为彩色视频
一、需求描述 设计一个简单的视频上色应用,用户可以通过网页界面上传黑白视频,系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观,不需要了解技术细节。 效果图 二、实现思路 总体思路: 用户通过Gradio界面上…...
2025.6.9总结(利与弊)
凡事都有两面性。在大厂上班也不例外。今天找开发定位问题,从一个接口人不断溯源到另一个 接口人。有时候,不知道是谁的责任填。将工作内容分的很细,每个人负责其中的一小块。我清楚的意识到,自己就是个可以随时替换的螺丝钉&…...
