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

Leetcode 188 买卖股票的最佳时机 IV

题意理解: 

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

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

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

        

        这道题的特别之处是,最多可以买卖k次,k是一个可以变化的值,所以使用j对k的数值进行遍历。

解题思路:

        (1)定义dp二维[][]数组

                dp[0][0]表示不操作

                dp[i][j=2(k-1)+1]表示第k次买入

                dp[i][j=2(k-1)+2]表示第k次卖出

          (2) 初始化

                dp[0][0]=0

                dp[0][j=2(k-1)+1]=-prices[i]

                dp[0][j=2(k-1)+2]=0

          (3) 递推公式

                dp[i][j=2(k-1)+1]

                =max(延续之前状态,买入)

                =max(dp[i-][j=2(k-1)+1],dp[i-1][j=2(k-1)]-prices[i])

                dp[i][j=2(k-1)+2]=-prices[i]

                =max(延续之前状态,卖出)

                =max(dp[i-][j=2(k-1)+2],dp[0-1][j=2(k-1)+1]+prices[i])

1.解题

public int maxProfit(int k, int[] prices) {int[][] dp=new int[prices.length][2*k+1];for(int i=0;i<=2*k;i++){if(i%2==0)dp[0][i]=0;else dp[0][i]=-1*prices[0];}for(int i=1;i<prices.length;i++){dp[i][0]=dp[i-1][0];for(int j=0;j<2*k;j+=2){dp[i][j+1]=Math.max(dp[i-1][j+1],dp[i-1][j]-prices[i]);dp[i][j+2]=Math.max(dp[i-1][j+2],dp[i-1][j+1]+prices[i]);}}int max=0;for(int i=0;i<=2*k;i++)max=Math.max(max,dp[prices.length-1][i]);return max;}

2.分析

时间复杂度:O(kn)

空间复杂度:O(2kn)

相关文章:

Leetcode 188 买卖股票的最佳时机 IV

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

win32编程系统BUG(Win32 API中的WM_SETTEXT消息)

由于频繁使用Win32 API中的WM_SETTEXT消息&#xff0c;导致内存占用直线上升。 暂未找到有效解决方案。...

Linux防火墙开放

记录一次问题 写的网络服务无法通信 代码没问题&#xff0c;IP绑定、端口绑定没问题&#xff0c;就是无法进行通信&#xff0c;这里要分2步走。 服务器控制台开放 进入防火墙 添加规则&#xff0c;这里以开放udp的8899端口为例 这里在服务器后台就已经开放了&#xff0c;但此时…...

通过 docker-compose 部署 Flink

概要 通过 docker-compose 以 Session Mode 部署 flink 前置依赖 Docker、docker-composeflink 客户端docker-compose.yml version: "2.2" services:jobmanager:image: flink:1.17.2ports:- "8081:8081"command: jobmanagervolumes:- ${PWD}/checkpoin…...

HarmonyOS ArkTS修改App的默认加载的界面(二十)

前言&#xff1a;在Android开发中想要修改默认启动页&#xff0c;只需要在AndroidManifest.xml中设置即可 只需要在启动的activity种添加如下属性即可 <intent-filter><action android:name"android.intent.action.MAIN" /><category android:name&qu…...

【前端高频面试题--Vue基础篇】

&#x1f680; 作者 &#xff1a;“码上有前” &#x1f680; 文章简介 &#xff1a;前端高频面试题 &#x1f680; 欢迎小伙伴们 点赞&#x1f44d;、收藏⭐、留言&#x1f4ac;前端高频面试题--Vue基础篇 Vue基本原理双向绑定与MVVM模型Vue的优点计算属性与监听属性计算属性监…...

Spring Boot 实现热插拔 AOP

现在有这么一个需求:就是我们日志的开与关是交给使用人员来控制的,而不是由我们开发人员固定写死的。大家都知道可以用aop来实现日志管理,但是如何动态的来实现日志管理呢?aop源码中的实现逻辑中有这么一个步骤,就是会依次扫描Advice的实现类,然后执行。我们要做的就是自…...

2月05日,每日信息差

第一、全球首套5G及6G天地一体网络低轨试验卫星发射入轨、。据了解&#xff0c;“中国移动01星”是全球首颗可验证5G天地一体演进技术的试验卫星&#xff0c;它搭载的基站可以利用卫星的广覆盖优势把5G信号传送到地面网络无法覆盖到的地方&#xff1b;另外一颗“‘星核’验证星…...

使用Python进行数据的描述性分析,用少量的描述性指标来概括大量的原始数据

在进行数据分析时&#xff0c;当研究者得到的数据量很小时&#xff0c;可以通过直接观察原始数据来获得所有的信息。但是&#xff0c;当得到的数据量很大时&#xff0c;就必须借助各种描述性指标来完成对数据的描述工作。用少量的描述性指标来概括大量的原始数据&#xff0c;对…...

【JS逆向三】逆向某某网站的sign参数,并模拟生成仅供学习

逆向日期&#xff1a;2024.02.06 使用工具&#xff1a;Node.js 类型&#xff1a;webpack 文章全程已做去敏处理&#xff01;&#xff01;&#xff01; 【需要做的可联系我】 可使用AES进行解密处理&#xff08;直接解密即可&#xff09;&#xff1a;AES加解密工具 1、打开某某…...

移动光猫gs3101超级密码及改桥接模式教程

文章目录 超级管理员账号改桥接模式路由器连接光猫&#xff0c;PPPOE拨号即可&#xff01;附录&#xff1a;如果需要改桥接的话不知道拨号密码咋办打开光猫Telnet功能Telnet 登录 参考文章 移动光猫吉比特GS3101超级账号获取更改桥接 移动光猫gs3101超级密码及改桥接模式教程 …...

leetcode 153

153 寻找旋转排序数组中的最小值 这道题&#xff0c;如果我们熟悉数组 api&#xff0c;可以直接用 Arrays.sort()秒杀&#xff0c;这个方法使用了双轴快速排序算法。 解法1如下&#xff1a; class Solution {public int findMin(int[] nums) {Arrays.sort(nums);return nums…...

【MySQL】数据库的基础——数据库的介绍、MySQL的介绍和架构、SQL分类、MySQL的基本使用、MySQL的存储引擎

文章目录 MySQL1. 数据库的介绍1.2 主流数据库 2. MySQL的介绍2.1 MySQL架构2.2 SQL分类2.3 MySQL的基本使用2.4 MySQL存储引擎 MySQL 1. 数据库的介绍 数据库&#xff08;Database&#xff0c;简称DB&#xff09;是按照数据结构来组织、存储和管理数据的仓库。它是长期存储在计…...

后端的技术设计文档

一、 背景 1.简介 2.业务规划(非必需) 3.工作项拆解 拆解成多个工作项&#xff0c;每个工作项&#xff0c;需要多少人力。 4.资源评估(非必需) 有没有新的服务 二、架构设计 1.架构图(非必需&#xff0c;新服务比较需要) 2.技术选型 SpringCloud、Redis、Mysql、Myba…...

Windows10安装PCL1.14.0及点云配准

一、下载visual studio2022 下载网址&#xff1a;Visual Studio: 面向软件开发人员和 Teams 的 IDE 和代码编辑器 (microsoft.com) 安装的时候选择"使用C的桌面开发“&#xff0c;同时可以修改文件路径&#xff0c;可以放在D盘。修改文件路径的时候&#xff0c;共享组件、…...

C语言第二十二弹---指针(六)

✨个人主页&#xff1a; 熬夜学编程的小林 &#x1f497;系列专栏&#xff1a; 【C语言详解】 【数据结构详解】 指针 1. 回调函数是什么&#xff1f; 2、qsort使用举例 2.1、使用qsort函数排序整型数据 2.2 使用qsort排序结构体数据 3、qsort函数的模拟实现 总结 1. 回…...

Qt Windows和Android使用MuPDF预览PDF文件

文章目录 1. Windows MuPDF编译2. Android MuPDF编译3. 引用 MuPDF 库4. 解析本地PDF文件 1. Windows MuPDF编译 使用如下命令将MuPDF的源码克隆到本地 git clone --recursive git://git.ghostscript.com/mupdf.git直接用VS&#xff0c;打开 mupdf/platform/win32/mupdf.sln …...

MongoDB聚合:$replaceWith

r e p l a c e W i t h ‘ 可以将输入文档替换为指定的文档。该操作可以替换输入文档的所有字段&#xff0c;包括 ‘ i d ‘ 字段。使用 ‘ replaceWith可以将输入文档替换为指定的文档。该操作可以替换输入文档的所有字段&#xff0c;包括_id字段。使用 replaceWith‘可以将输…...

Vue 进阶系列丨实现简易VueRouter

‍‍Vue 进阶系列教程将在本号持续发布&#xff0c;一起查漏补缺学个痛快&#xff01;若您有遇到其它相关问题&#xff0c;非常欢迎在评论中留言讨论&#xff0c;达到帮助更多人的目的。若感本文对您有所帮助请点个赞吧&#xff01; 2013年7月28日&#xff0c;尤雨溪第一次在 G…...

unity editor 编辑器 GUID localID LocalFileId 查找问题

//传入对象实例化ID 可以获取到 guid localid guid预设的ID localid 预设内的ID //这个方法有个问题如果在预设编辑器状态下 可能出现查不到 guid localid 原因可能 传入对象是是编辑状态下instanceid 并不是保存状态下的 UnityEditor.AssetDatabase.TryGetGUIDAndLocalF…...

STM32+rt-thread判断是否联网

一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

云原生玩法三问:构建自定义开发环境

云原生玩法三问&#xff1a;构建自定义开发环境 引言 临时运维一个古董项目&#xff0c;无文档&#xff0c;无环境&#xff0c;无交接人&#xff0c;俗称三无。 运行设备的环境老&#xff0c;本地环境版本高&#xff0c;ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

jmeter聚合报告中参数详解

sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample&#xff08;样本数&#xff09; 表示测试中发送的请求数量&#xff0c;即测试执行了多少次请求。 单位&#xff0c;以个或者次数表示。 示例&#xff1a;…...

【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案

目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后&#xff0c;迭代器会失效&#xff0c;因为顺序迭代器在内存中是连续存储的&#xff0c;元素删除后&#xff0c;后续元素会前移。 但一些场景中&#xff0c;我们又需要在执行删除操作…...

LLaMA-Factory 微调 Qwen2-VL 进行人脸情感识别(二)

在上一篇文章中,我们详细介绍了如何使用LLaMA-Factory框架对Qwen2-VL大模型进行微调,以实现人脸情感识别的功能。本篇文章将聚焦于微调完成后,如何调用这个模型进行人脸情感识别的具体代码实现,包括详细的步骤和注释。 模型调用步骤 环境准备:确保安装了必要的Python库。…...

基于单片机的宠物屋智能系统设计与实现(论文+源码)

本设计基于单片机的宠物屋智能系统核心是实现对宠物生活环境及状态的智能管理。系统以单片机为中枢&#xff0c;连接红外测温传感器&#xff0c;可实时精准捕捉宠物体温变化&#xff0c;以便及时发现健康异常&#xff1b;水位检测传感器时刻监测饮用水余量&#xff0c;防止宠物…...

Java多线程实现之Runnable接口深度解析

Java多线程实现之Runnable接口深度解析 一、Runnable接口概述1.1 接口定义1.2 与Thread类的关系1.3 使用Runnable接口的优势 二、Runnable接口的基本实现方式2.1 传统方式实现Runnable接口2.2 使用匿名内部类实现Runnable接口2.3 使用Lambda表达式实现Runnable接口 三、Runnabl…...