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

leetCode 188.买卖股票的最佳时机 IV 动态规划 + 状态压缩

给你一个整数数组 prices 和一个整数 k ,其中 prices[i] 是某支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说,你最多可以买 k 次,卖 k 次。

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

示例 1:

输入:k = 2, prices = [2,4,1]
输出:2
解释:在第 1 天 (股票价格 = 2) 的时候买入,在第 2 天 (股票价格 = 4) 的时候卖出,这笔交易所能获得利润 = 4-2 = 2 。

示例 2:

输入:k = 2, prices = [3,2,6,5,0,3]
输出:7
解释:在第 2 天 (股票价格 = 2) 的时候买入,在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。随后,在第 5 天 (股票价格 = 0) 的时候买入,在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

 >>思路和分析

这道题目是 的进阶版,这里要求至多有k次交易

>>动规五部曲

1.确定dp数组以及下标的含义

一天 一共有 j 个 状态 ,dp[i][j] 中 i 表示 第 i 天,j 为[0 - 2*k] 个状态,dp[i][j]表示第 i 天状态 j所剩最大现金

  • 0.没有操作(其实也可以不设置这个状态)
  • 1.第一次持有股票
  • 2.第一次不持有股票
  • 3.第二次持有股票
  • 4.第二次不持有股票
  • ...

"持有" : 不代表就是当天"买入"!可能昨天就买入了,今天保持有的状态

  • ① 我们可以发现,除了0以外,偶数就是不持有,奇数就是持有
  • ② 题目要求是至多有k笔交易,那么j的范围就定义为 2*k+1就可以
vector<vector<int>> dp(prices.size(), vector<int>(2 * k + 1, 0));

2.确定递推公式 

 同理类比剩下的状态,代码如下:

for (int j = 0; j < 2 * k - 1; j += 2) {dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
}

推导思路:

-----------------------------------------------------------
第 i 天 的五种状态
dp[i][0] 不操作dp[i][1] 第一天持有股票时剩下的最大金钱
dp[i][1]         dp[i-1][1]dp[i-1][0] - prices[i]dp[i][2] 第一天不持有股票时剩下的最大金钱
dp[i][2]         dp[i-1][2]dp[i-1][1] + prices[i]dp[i][3] 第二天持有股票时剩下的最大金钱
dp[i][3]         dp[i-1][3]dp[i-1][2] - prices[i]
dp[i][4] 第二天不持有股票时剩下的最大金钱
dp[i][4]         dp[i-1][4]dp[i-1][3] + prices[i]-----------------------------------------------------------
dp[i][j+1]       dp[i-1][j+1]dp[i-1][j] - prices[i]dp[i][j+2]       dp[i-1][j+2]dp[i-1][j+1] + prices[i]dp[i][j+1] = max(dp[i-1][j+1],dp[i-1][j] - prices[i]);
dp[i][j+2] = max(dp[i-1][j+2],dp[i-1][j+1] + prices[i]);
-----------------------------------------------------------

 3.dp数组初始化

dp[0][0] = 0;
dp[0][1] = -prices[0];
dp[0][2] = 0;
dp[0][3] = -prices[0];
dp[0][4] = 0;
...

同理推出dp[0][j]当 j 为奇数时都初始化为 -prices[0]。代码如下:

for (int j = 1; j < 2 * k; j += 2) {dp[0][j] = -prices[0];
}

4.确定遍历顺序

从递归公式其实已经可以看出,一定是从前向后遍历因为dp[i],依靠dp[i - 1]的数值。

5.举例推导dp数组

(1)以输入[1,2,3,4,5],k = 2为例

(2)以输入[3,3,5,0,0,3,1,4],k = 2为例

最后一次卖出,一定是利润最大的,dp[prices.size() - 1][2 * k]即红色部分就是最后求解。 

class Solution {
public:int maxProfit(int k, vector<int>& prices) {if (prices.size() == 0) return 0;vector<vector<int>> dp(prices.size(), vector<int>(2 * k + 1, 0));for (int j = 1; j < 2 * k; j += 2) {dp[0][j] = -prices[0];}for (int i = 1;i < prices.size(); i++) {for (int j = 0; j < 2 * k - 1; j += 2) {dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);}}return dp[prices.size() - 1][2 * k];}
};
  • 时间复杂度: O(n * k),其中 n 为 prices 的长度
  • 空间复杂度: O(n * k)

>>状态压缩

class Solution {
public:// 状态压缩int maxProfit(int k, vector<int>& prices) {if (prices.size() == 0) return 0;int len = prices.size();vector<int>dp(2 * k + 1,0);for(int j = 1;j < 2 * k;j += 2) {dp[j] = -prices[0];}for(int i=1;i<len;i++) {for(int j=0;j < 2*k-1;j += 2) {dp[j+1] = max(dp[j+1],dp[j] - prices[i]);dp[j+2] = max(dp[j+2],dp[j+1] + prices[i]);}}return dp[2*k];}
};
  • 时间复杂度: O(n * k),其中 n 为 prices 的长度
  • 空间复杂度: O(k)

参考和推荐文章、视频

动态规划来决定最佳时机,至多可以买卖K次!| LeetCode:188.买卖股票最佳时机4_哔哩哔哩_bilibili

代码随想录 (programmercarl.com) 

来自代码随想录课堂截图:

相关文章:

leetCode 188.买卖股票的最佳时机 IV 动态规划 + 状态压缩

给你一个整数数组 prices 和一个整数 k &#xff0c;其中 prices[i] 是某支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说&#xff0c;你最多可以买 k 次&#xff0c;卖 k 次。 注意&#xff1a;你不能同时参与多…...

Lua学习笔记:debug.sethook函数

前言 本篇在讲什么 使用Lua的debug.setHook函数 本篇需要什么 对Lua语法有简单认知 依赖Sublime Text工具 本篇的特色 具有全流程的图文教学 重实践&#xff0c;轻理论&#xff0c;快速上手 提供全流程的源码内容 ★提高阅读体验★ &#x1f449; ♠ 一级标题 &…...

信息化发展74

产业数字化 产业数字化是指在新一代数字科技支撑和引领下&#xff0c;以数据为关键要素&#xff0c;以价值释放为核心&#xff0c;以数据赋能为主线&#xff0c;对产业链上下游的全要素数字化升级、转型和再造的过程。产业数字化作为实现数字经济和传统经济深度融合发展的重要…...

Go-Ldap-Admin | openLDAP 同步钉钉、企业微信、飞书组织架构实践和部分小坑

目录 一、Docker-compose快速拉起demo测试环境 二、原生部署流程 安装MySQL&#xff1a;5.7数据库 安装openLDAP 修改域名&#xff0c;新增con.ldif 创建一个组织 安装OpenResty 下载后端 下载前端 部署后端 部署前端 三、管理动态字段 钉钉 企业微信 飞书 四、…...

elasticsearch+logstash+kibana整合(ELK的使用)第一课

一、安装elasticsearch 0、创建目录&#xff0c;统一放到/data/service/elk 1、下载安装包 wget https://artifacts.elastic.co/downloads/elasticsearch/elasticsearch-7.1.0-linux-x86_64.tar.gz2、解压 tar -xzvf elasticsearch-7.1.0-linux-x86_64.tar.gz3、新建用户和组…...

宝塔 php修改了php.ini配置不生效

最近在使用hypref&#xff0c;php的版本是7.4 服务器linux&#xff0c;用宝塔安装完php,并装完swoole插件后 安装了swoole后&#xff0c;需要在php.ini中修改一下配置文件 添加 swoole.use_shortnameOff 但是添加了&#xff0c;重启php,依然不生效 解决方法是&#xff1a; 同时…...

Unrecognized option ‘stream_loop‘.(版本不匹配,利用make编译安装)

执行如下命令&#xff1a; ffmpeg -re -stream_loop -1 -i 1.mp4 -vcodec copy -acodec copy -f rtsp -rtsp_transport tcp rtsp://localhost:8554/live1.sdp报如下错误&#xff1a;Unrecognized option ‘stream_loop’. 查看ffmpeg版本&#xff1a;ffmpeg -version 显示&am…...

【考研数学】概率论与数理统计 —— 第三章 | 二维随机变量及其分布(2,常见的二维随机变量及二维变量的条件分布和独立性)

文章目录 引言四、常见的二维随机变量4.1 二维均匀分布4.2 二维正态分布 五、二维随机变量的条件分布5.1 二维离散型随机变量的条件分布律5.2 二维连续型随机变量的条件分布 六、随机变量的独立性6.1 基本概念6.2 随机变量独立的等价条件 写在最后 引言 有了上文关于二维随机变…...

力扣 -- 10. 正则表达式匹配

解题步骤&#xff1a; 参考代码&#xff1a; class Solution { public:bool isMatch(string s, string p) {int ms.size();int np.size();//处理后续映射关系s s;//处理后续映射关系p p;vector<vector<bool>> dp(m1,vector<bool>(n1));//初始化dp[0][0]true…...

Spring源码分析(四) Aop全流程

一、Spring AOP基础概念 1、基础概念 连接点(Join point)&#xff1a;能够被拦截的地方&#xff0c;Spring AOP 是基于动态代理的&#xff0c;所以是方法拦截的&#xff0c;每个成员方法都可以称之为连接点&#xff1b;切点(Poincut)&#xff1a;每个方法都可以称之为连接点&…...

定义现代化实时数据仓库,SelectDB 全新产品形态全面发布

导读&#xff1a;9 月 25 日&#xff0c;2023 飞轮科技产品发布会在线上正式召开&#xff0c;本次产品发布会以 “新内核、新图景” 为主题&#xff0c;飞轮科技 CEO 马如悦全面解析了现代化数据仓库的演进趋势&#xff0c;宣布立足于多云之上的 SelectDB Cloud 云服务全面开放…...

Linux系统编程(七):线程同步

参考引用 UNIX 环境高级编程 (第3版)黑马程序员-Linux 系统编程 1. 同步概念 所谓同步&#xff0c;即同时起步、协调一致。不同的对象&#xff0c;对 “同步” 的理解方式略有不同 设备同步&#xff0c;是指在两个设备之间规定一个共同的时间参考数据库同步&#xff0c;是指让…...

Arcgis克里金插值报错:ERROR 999999: 执行函数时出错。 表名无效。 空间参考不存在。 ERROR 010429: GRID IO 中存在错误

ERROR 999999: 执行函数时出错。 问题描述 表名无效。 空间参考不存在。 ERROR 010429: GRID IO 中存在错误: WindowSetLyr: Window cell size does not match layer cell size. name: c:\users\lenovo\appdata\local\temp\arc2f89\t_t164, adepth: 32, type: 1, iomode: 6, …...

【网络协议】ARP协议

为什么网络需要同时借助MAC地址这种物理地址和IP地址这种逻辑地址进行通信&#xff1f; 尽管目前MAC地址可以通过逻辑的方式进行修改&#xff0c;但它最初是被设计为不可人为更改的硬件地址。虽然MAC地址也可以满足唯一性的要求&#xff0c;但由于它不可由管理员根据需求通过逻…...

安防视频/集中云存储平台EasyCVR(V3.3)部分通道显示离线该如何解决?

安防视频监控/视频集中存储/云存储/磁盘阵列EasyCVR平台可拓展性强、视频能力灵活、部署轻快&#xff0c;可支持的主流标准协议有国标GB28181、RTSP/Onvif、RTMP等&#xff0c;以及支持厂家私有协议与SDK接入&#xff0c;包括海康Ehome、海大宇等设备的SDK等。平台既具备传统安…...

软件测试经典面试题:如何进行支付功能的测试?

非现金支付时代&#xff0c;非现金支付已经成为了生活不可或缺的一部分&#xff0c;我们只需要一台手机便可走遍全国各地&#xff08;前提是支付宝&#xff0c;微信有钱<00>&#xff09;,那么作为测试人员&#xff0c;支付测试也是非常重要的一环&#xff0c;那么下面我就…...

SolidWorks 入门笔记03:生成工程图和一键标注

默认情况下&#xff0c;SOLIDWORKS系统在工程图和零件或装配体三维模型之间提供全相关的功能&#xff0c;全相关意味着无论什么时候修改零件或装配体的三维模型&#xff0c;所有相关的工程视图将自动更新&#xff0c;以反映零件或装配体的形状和尺寸变化&#xff1b;反之&#…...

【Java】对象内存图多个对象同一内存地址

目录 学生类 单个对象内存图 多个对象指向同一个内存地址 学生类 Student.java如下&#xff1a; package com.面向对象;public class Student {String name;int age;public void work() {System.out.println("开始敲代码...");} }StudentDemo.java如下&#xff…...

Python 笔记05(装饰器的使用)

一 装饰器的使用 (property) property 是 Python 中用于创建属性的装饰器。它的作用是将一个类方法转换为类属性&#xff0c;从而可以像 访问属性一样访问该方法&#xff0c;而不需要使用函数调用的语法。使用 property 主要有以下好处&#xff1a; 封装性和隐藏实现细节&…...

记忆化搜索,901. 滑雪

901. 滑雪 - AcWing题库 给定一个 R 行 C 列的矩阵&#xff0c;表示一个矩形网格滑雪场。 矩阵中第 i行第 j 列的点表示滑雪场的第 i 行第 j列区域的高度。 一个人从滑雪场中的某个区域内出发&#xff0c;每次可以向上下左右任意一个方向滑动一个单位距离。 当然&#xff0…...

计算机网络:连接世界的纽带

计算机网络的基础概念 计算机网络是一组相互连接的计算机&#xff0c;它们通过通信链路和协议进行数据交换和资源共享。以下是一些关键概念&#xff1a; 1. 节点和主机 网络中的计算机设备称为节点&#xff0c;通常是主机或服务器。主机是普通用户或终端设备&#xff0c;而服…...

SpringMVC 学习(三)注解开发

4. 注解开发 4.1 环境搭建 (1) 新建 maven 模块 springmvc-03-annotation (2) 确认依赖 确认方法同 3(2)&#xff0c;手动导入发布依赖见3(11) <!--资源过滤--> <build><resources><resource><directory>src/main/java</directory>&…...

0x84加密数据传输服务

为了在安全模式下实现一些诊断服务&#xff0c;在服务端和客户端应用程序之间添加了Security sub-layer。在客户端与服务端之间进行诊断服务数据传输有两种方法&#xff1a; 1、非安全模式下数据传输   应用程序使用诊断服务(diagnostic Services)和应用层服务原语(Applicati…...

Vue.js快速入门:构建现代Web应用

Vue Vue.js是一款流行的JavaScript框架&#xff0c;用于构建现代的、交互式的Web应用程序。它具有简单易学的特点&#xff0c;同时也非常强大&#xff0c;能够帮助开发者构建高效、可维护的前端应用。本篇博客将带你快速入门Vue.js&#xff0c;并演示如何构建一个简单的Vue应用…...

Scala第五章节

Scala第五章节 scala总目录 章节目标 掌握方法的格式和用法掌握函数的格式和用法掌握九九乘法表案例 1. 方法 1.1 概述 实际开发中, 我们需要编写大量的逻辑代码, 这就势必会涉及到重复的需求. 例如: 求10和20的最大值, 求11和22的最大值, 像这样的需求, 用来进行比较的逻…...

erlang练习题(三)

题目一 查询列表A是否为列表B的前缀 解答 isPrefix([], List2) -> io:format("A is prefix of B ~n");isPrefix([H1 | ListA], [H2 | ListB]) ->case H1 H2 oftrue -> isPrefix(ListA, ListB);false -> io:format("A is not prefix of B ~n&quo…...

What Is A DNS Amplification DDoS Attack?

什么是 DNS 放大攻击&#xff1f; 域名系统 &#xff08;DNS&#xff09; 是用于在网站的机器可读地址&#xff08;例如 191.168.0.1&#xff1a;80&#xff09;和人类可读名称&#xff08;例如 radware.com&#xff09;之间进行解析的目录在 DNS 放大攻击中&#xff0c;攻击者…...

jvm笔记

好处&#xff1a; 跨平台 内存管理机制&#xff0c;垃圾回收功能 数组下标越界检查 多态 名词解释&#xff1a; jvm java虚拟机&#xff0c;是java程序的运行环境 jre jvm基础类库 jdk jre编译工具 javase jdkide工具 javaee javase应用服务器 jvm的内存结构&#xff1a; 程序…...

WPF中的控件

内容控件&#xff1a;label、border Window控件 Label控件 Border控件 内容控件 Button控件 点击取消按钮关闭程序&#xff1b;点击登录按钮打开BorderWindow窗口。 TextBox控件 PasswordBox控件 TextBlock控件 加载窗口时显示TextBlock中的内容 RadioButton控件 CheckBox控件…...

Java下对象的序列化和反序列化(写出和读入)

代码如下&#xff1a; public class MyWork {public static void main(String[] args) throws IOException, ClassNotFoundException {//序列化File f new File("testFile/testObject.txt");ObjectOutputStream oos new ObjectOutputStream(new FileOutputStream(…...

哪家网站建设/个人博客登录入口

点击蓝字关注我们吧&#xff01;第一种打印hello world的方法启动Python程序并打印Hello world&#xff01;第二种打印hello world的方法1&#xff0c;新建一个hello.py文件&#xff0c;使用notepad打开&#xff08;或者新建一个hello.txt文档&#xff0c;编写完代码后&#xf…...

做网站 需要注意什么/国内最新新闻消息今天的

问题中没有关于您的用例的详细信息,因此您可能需要调整以下示例的某些部分。一种方法是使用元素所属的窗口作为键对元素进行分组。然后,我们利用filesystems.FileSystems.create来控制我们要如何写文件。data [{event: {}.format(event), timestamp: time.time() 4*event} fo…...

墨刀做网站/近期网络舆情事件热点分析

jQuery(三) javascript跨域问题(JSONP解决)参考文章&#xff1a; &#xff08;1&#xff09;jQuery(三) javascript跨域问题(JSONP解决) &#xff08;2&#xff09;https://www.cnblogs.com/whgk/p/7102625.html 备忘一下。...

深圳哪里有网站建设/产品代理推广方案

题目&#xff1a;https://www.luogu.org/problemnew/show/P3205 同 关路灯&#xff0c;精髓在于左端点和右端点。 注意&#xff01;&#xff01;&#xff01;L2时有重复&#xff01; #include<iostream> #include<cstdio> using namespace std; int n,h[1005]; lon…...

山东搜点网站建设/友情链接交换

问题描述 在某个线上网站&#xff0c;电商网站&#xff0c;当进入确定订单页面&#xff0c;填写买家留言以后&#xff0c;页面跳转到订单支付页面&#xff0c;下面的fixed定位的支付按钮就会消失&#xff0c;该问题烦恼了很久&#xff0c;于是。。 百度之&#xff1a; 这几天…...

网站建设云主机云服务器/网站外链的优化方法

我国基因编辑技术的研发领先全球&#xff0c;但由于尚未出台基因编辑产品管理政策&#xff0c;相关产业面临技术研究领先、管理滞后、应用空白的局面。与会专家学者、企业代表纷纷结合国外基因编辑监管措施建言献策&#xff0c;呼吁基因编辑政策早日出台。 “目前&#xff0c;…...