Leetcode 188. 买卖股票的最佳时机 Ⅳ 状态机dp C++实现

Leetcode 188.买卖股票的最佳时机 Ⅳ

问题:给你一个整数数组 prices 和一个整数 k ,其中 prices[i] 是某支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说,你最多可以买 k 次,卖 k 次。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

算法:递归搜索 + 保存计算结果 = 记忆化搜索

        在 Leetcode122. 买卖股票 状态机dp C++实现 的基础上,添加一个参数 j,表示当前可以至多交易 j 次。

注意:由于最后未持有股票,手上的股票一定会卖掉,所以代码中的 j-1 可以是在买股票的时候,也可以是在卖股票的时候,这两种写法都是可以的。

以下代码参数 j 的修改时机为买入时。

时间复杂度:O(nk),其中 n 为 prices 的长度。

空间复杂度:O(nk)

代码:

class Solution {
public:int maxProfit(int k, vector<int>& prices) {int n = prices.size();vector<vector<array<int, 2>>> memo(n, vector<array<int, 2>>(k + 1, {-1, -1})); // -1 表示还没有计算过auto dfs = [&](auto&& dfs, int i, int j, bool hold) -> int {if (j < 0)  return INT_MIN / 2; // 除 2 防止溢出if (i < 0)  return hold ? INT_MIN / 2 : 0;int& res = memo[i][j][hold]; // 注意这里是引用if (res != -1)  return res;// 之前计算过if (hold)   return res = max(dfs(dfs, i - 1, j, true), dfs(dfs, i - 1, j - 1, false) - prices[i]);return res = max(dfs(dfs, i - 1, j, false), dfs(dfs, i - 1, j, true) + prices[i]);};return dfs(dfs, n - 1, k, false);}
};

算法:1:1 翻译成递推

时间复杂度:O(nk),其中 n 为 prices 的长度。

空间复杂度:O(nk)

代码:

class Solution {
public:int maxProfit(int k, vector<int>& prices) {int n = prices.size();vector<vector<array<int, 2>>> dp(n + 1, vector<array<int, 2>>(k + 2, {INT_MIN / 2, INT_MIN / 2}));for(int j = 1;j <= k + 1;j++)   dp[0][j][0] = 0;for(int i = 0;i < n;i++)for(int j = 1;j <= k + 1;j++){dp[i + 1][j][0] = max(dp[i][j][0],dp[i][j][1] + prices[i]);dp[i + 1][j][1] = max(dp[i][j][1],dp[i][j - 1][0] - prices[i]);}return dp[n][k + 1][0];}
};

算法:空间优化

必须倒序遍历。

时间复杂度:O(nk),其中 n 为 prices 的长度。

空间复杂度:O(k)

代码:

class Solution {
public:int maxProfit(int k, vector<int>& prices) {vector<array<int, 2>> dp(k + 2, {INT_MIN / 2, INT_MIN / 2});for(int j = 1;j <= k + 1;j++)   dp[j][0] = 0;for(int p : prices)for(int j = k + 1;j > 0;j--){dp[j][0] = max(dp[j][0],dp[j][1] + p);dp[j][1] = max(dp[j][1],dp[j - 1][0] - p);}return dp[k + 1][0];}
};

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

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

相关文章

准备好了吗?JAVA从业AI开发的学习路线详解

作为一个拥有扎实 Java 基础的人&#xff0c;想要涉足人工智能&#xff08;AI&#xff09;应用开发&#xff0c;你已经在编程能力方面打下了很好的基础。Java 是一种通用的、强类型的语言&#xff0c;非常适合于开发高性能的应用程序&#xff0c;尤其是在后端服务和大规模分布式…

C++:IO流

目录 C语言的输入输出 流是什么 CIO流 C标准IO流 C文件IO流 stringstream的介绍 C语言的输入输出 C 语言中我们用到的最频繁的输入输出方式就是 scanf () 与 printf() 。 scanf(): 从标准输入设备 ( 键 盘 ) 读取数据&#xff0c;并将值存放在变量中 。 printf(): 将…

linux驱动之模块化编程

我们写的驱动程序&#xff0c;对linux操作系统而言&#xff0c;都是一个一个模块。 我们写应用程代码的时候是要有main函数入口&#xff0c;但是驱动模块有自己的入口。所以在编译驱动模块的时候就要使用到内核的makefile&#xff0c;来编译我们的模块。 我们在命令行敲&#x…

RS®FSWP 相位噪声分析仪和 VCO 测试仪信号源和组件的高端分析

FSWP 相位噪声分析仪和VCO测试仪 价格实惠&#xff0c;性能出众 R&SFSWP 相位噪声分析仪和 VCO 测试仪结合噪声极低的内部源与互相关技术&#xff0c;具备高灵敏度。它可在数秒内测量高度稳定的信号源的相位噪声。 R&SFSWP 还具备脉冲信号测量、加性相位噪声&…

C++初阶:string类的模拟实现

✨✨小新课堂开课了&#xff0c;欢迎欢迎~✨✨ &#x1f388;&#x1f388;养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; 所属专栏&#xff1a;C&#xff1a;由浅入深篇 小新的主页&#xff1a;编程版小新-CSDN博客 前言&#xff1a; 前面已经对string类进行了…

[数据集][目标检测]井盖丢失未盖破损检测数据集VOC+YOLO格式2890张5类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;2890 标注数量(xml文件个数)&#xff1a;2890 标注数量(txt文件个数)&#xff1a;2890 标注…

QGIS 如何连接空间库,并实时编辑空间表?编辑后库表如何刷新,保证是最新数据?

文章目录 一、什么是 qgis&#xff1f;二、qgis 如何连接数据库三、实时编辑空间表四、编辑后库表如何刷新&#xff0c;保证是最新数据&#xff1f;五、总结 一、什么是 qgis&#xff1f; QGIS&#xff08;原称Quantum GIS&#xff09;是一个用户界面友好的开源桌面端软件&…

htop、free -h对于可用内存显示不同的区别

htop中Mem包含了缓存和缓存区&#xff0c; free -h查看 used free buff/cache 上面htop显示的mem&#xff0c; 1、我看我还能用多少内存&#xff0c;看哪里 看free -h 中的free 2、buff/cache 是啥 缓存缓存区占用&#xff0c;htop显示的效果是把这个也算在一块了&#…

TIDB的整体架构和主要功能

1. 基础架构 PD &#xff1a;负责集群管理和调度。TiDB Server &#xff1a;负责 SQL 查询处理。TiKV/TiFlash&#xff1a;负责数据存储和事务处理。 1.1 PD (Placement Driver) Server 1.1.1 基础介绍 整个 TiDB 集群的元信息管理模块&#xff0c;负责存储每个 TiKV 节点实时…

哪款骨传导耳机适合运动?健身党无广安利五款有用的骨传导耳机!

作为一名耳机爱好者&#xff0c;我的耳机收藏可以说是丰富多样&#xff0c;从追求极致音质的头戴式&#xff0c;到便于携带的入耳式&#xff0c;再到近年来兴起的骨传导耳机&#xff0c;我都有所体验。在众多选择中&#xff0c;我最终偏爱上了骨传导耳机&#xff0c;它以其独特…

vue3 使用 codemirror 实现yaml文件的在线编辑

vue3 使用 codemirror 实现yaml文件的在线编辑 1. 使用情形2. 插件下载3. 封装yaml编辑器组件4. 父组件使用5. js-yaml 使用6. 备注 1. 使用情形 需要对yaml文件进行在线编辑&#xff0c;并且进行基础格式验证 2. 插件下载 vue-codemirror 在线代码编辑器插件 js-yaml 用于转…

容联云容犀Copilot&Agent入选《中国 AI Agent 产品罗盘》

近日&#xff0c;InfoQ研究中心推出《中国AI Agent应用研究报告》&#xff0c;并在报告中对现行的中国AI Agent产品进行梳理总结&#xff0c;并形成《中国AI Agent产品罗盘》。 作为“营销服”领域垂直类Agent&#xff0c;容联云容犀Copilot&#xff06;Agent入选2024中国AI A…

java8+springboot2.3升级jdk17+springboot2.7.9踩坑

一.问题: java.lang.ExceptionInInitializerError: nullat java.base/java.lang.Class.forName0(Native Method)at java.base/java.lang.Class.forName(Class.java:375)。。。。。。内部保密。。。。at org.springframework.context.annotation.ParserStrategyUtils.invokeAwa…

封装智能指针 qt实现登录界面

1.封装独占智能指针——unique_ptr #include <iostream> #include <utility> // For std::move// 命名空间 namespace custom_memory { template <typename T> class myPtr { public:// 使用初始化列表进行初始化explicit myPtr(T* p nullptr) noexcept : …

ThinkPHP8出租屋管理系统

有需要请加文章底部Q哦 可远程调试 ThinkPHP8出租屋管理系统 一 介绍 此出租屋管理系统基于ThinkPHP8框架开发&#xff0c;数据库mysql&#xff0c;前端Vue3&#xff0c;前后端不分离&#xff0c;系统主要角色为管理员。房租计算器&#xff0c;房东记账收租管理&#xff0c;房…

NX二次开发—柱面中心线工具

设计一个柱面中心线工具,可以实现选择对象,画出圆柱的中心线,可以更改中心的线的颜色、线型、线宽和图层,是否延长,是否关联。 先在NX上进行界面设计 添加选择对象,并设置标题,选择设置为多选 添加组,在组里添加线条颜色/线型/线宽,设置颜色ColorValue和线型Value 这…

C++详解string(全面解析)

目录 string的概念&#xff1a; string的框架&#xff1a; 1、成员函数 2、迭代器&#xff08;Iterators&#xff09;​编辑 3、容量 4、元素访问 5、修改 6、非成员函数重载 string的构造和拷贝构造&#xff1a; string的析构&#xff1a; string的访问&#xff1a;…

单片机,传感器等低功耗管理

**有些客户需求&#xff0c;把设备做成低功耗管理&#xff0c;这样就可以节省电池的电量&#xff0c;也可以增加传感器的使用寿命 HCLK为CPU提供时钟&#xff0c;内核执行代码。当CPU不需要继续运行时&#xff0c;可以利用多种低功耗模式&#xff0c;等待某个事件触发 ① 睡眠…

单链表的实现(C语言)

目录 1.单链表 1.1 实现单链表 1.1.1 文件创建 1.1.2 链表功能了解 1.1.3 链表的结点 1.1.4 链表的函数声明 1.1.5 链表功能的实现 链表是一种链式结构&#xff0c;物理结构不连续&#xff0c;逻辑结构是连续的&#xff0c;在计算机中链表的实际存储是按照一个结点内存放…

pod install 报错处理

由于墙的原因&#xff0c;pod install 、 pod update经常报错 有效的解决方案(推荐)&#xff1a; 以SnapKit为例 找不报错的同事要以下两个文件&#xff08;指定的版本&#xff09; 1. /Users/xxx/Library/Caches/CocoaPods/Pods/Release/SnapKit 2. /Users/xxx/Library/Cac…