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
题意理解: 给你一个整数数组 prices 和一个整数 k ,其中 prices[i] 是某支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说,你最多可以买 k 次,卖 k 次。 注意…...
win32编程系统BUG(Win32 API中的WM_SETTEXT消息)
由于频繁使用Win32 API中的WM_SETTEXT消息,导致内存占用直线上升。 暂未找到有效解决方案。...
Linux防火墙开放
记录一次问题 写的网络服务无法通信 代码没问题,IP绑定、端口绑定没问题,就是无法进行通信,这里要分2步走。 服务器控制台开放 进入防火墙 添加规则,这里以开放udp的8899端口为例 这里在服务器后台就已经开放了,但此时…...
通过 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的默认加载的界面(二十)
前言:在Android开发中想要修改默认启动页,只需要在AndroidManifest.xml中设置即可 只需要在启动的activity种添加如下属性即可 <intent-filter><action android:name"android.intent.action.MAIN" /><category android:name&qu…...
【前端高频面试题--Vue基础篇】
🚀 作者 :“码上有前” 🚀 文章简介 :前端高频面试题 🚀 欢迎小伙伴们 点赞👍、收藏⭐、留言💬前端高频面试题--Vue基础篇 Vue基本原理双向绑定与MVVM模型Vue的优点计算属性与监听属性计算属性监…...
Spring Boot 实现热插拔 AOP
现在有这么一个需求:就是我们日志的开与关是交给使用人员来控制的,而不是由我们开发人员固定写死的。大家都知道可以用aop来实现日志管理,但是如何动态的来实现日志管理呢?aop源码中的实现逻辑中有这么一个步骤,就是会依次扫描Advice的实现类,然后执行。我们要做的就是自…...
2月05日,每日信息差
第一、全球首套5G及6G天地一体网络低轨试验卫星发射入轨、。据了解,“中国移动01星”是全球首颗可验证5G天地一体演进技术的试验卫星,它搭载的基站可以利用卫星的广覆盖优势把5G信号传送到地面网络无法覆盖到的地方;另外一颗“‘星核’验证星…...
使用Python进行数据的描述性分析,用少量的描述性指标来概括大量的原始数据
在进行数据分析时,当研究者得到的数据量很小时,可以通过直接观察原始数据来获得所有的信息。但是,当得到的数据量很大时,就必须借助各种描述性指标来完成对数据的描述工作。用少量的描述性指标来概括大量的原始数据,对…...
【JS逆向三】逆向某某网站的sign参数,并模拟生成仅供学习
逆向日期:2024.02.06 使用工具:Node.js 类型:webpack 文章全程已做去敏处理!!! 【需要做的可联系我】 可使用AES进行解密处理(直接解密即可):AES加解密工具 1、打开某某…...
移动光猫gs3101超级密码及改桥接模式教程
文章目录 超级管理员账号改桥接模式路由器连接光猫,PPPOE拨号即可!附录:如果需要改桥接的话不知道拨号密码咋办打开光猫Telnet功能Telnet 登录 参考文章 移动光猫吉比特GS3101超级账号获取更改桥接 移动光猫gs3101超级密码及改桥接模式教程 …...
leetcode 153
153 寻找旋转排序数组中的最小值 这道题,如果我们熟悉数组 api,可以直接用 Arrays.sort()秒杀,这个方法使用了双轴快速排序算法。 解法1如下: 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. 数据库的介绍 数据库(Database,简称DB)是按照数据结构来组织、存储和管理数据的仓库。它是长期存储在计…...
后端的技术设计文档
一、 背景 1.简介 2.业务规划(非必需) 3.工作项拆解 拆解成多个工作项,每个工作项,需要多少人力。 4.资源评估(非必需) 有没有新的服务 二、架构设计 1.架构图(非必需,新服务比较需要) 2.技术选型 SpringCloud、Redis、Mysql、Myba…...
Windows10安装PCL1.14.0及点云配准
一、下载visual studio2022 下载网址:Visual Studio: 面向软件开发人员和 Teams 的 IDE 和代码编辑器 (microsoft.com) 安装的时候选择"使用C的桌面开发“,同时可以修改文件路径,可以放在D盘。修改文件路径的时候,共享组件、…...
C语言第二十二弹---指针(六)
✨个人主页: 熬夜学编程的小林 💗系列专栏: 【C语言详解】 【数据结构详解】 指针 1. 回调函数是什么? 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,打开 mupdf/platform/win32/mupdf.sln …...
MongoDB聚合:$replaceWith
r e p l a c e W i t h ‘ 可以将输入文档替换为指定的文档。该操作可以替换输入文档的所有字段,包括 ‘ i d ‘ 字段。使用 ‘ replaceWith可以将输入文档替换为指定的文档。该操作可以替换输入文档的所有字段,包括_id字段。使用 replaceWith‘可以将输…...
Vue 进阶系列丨实现简易VueRouter
Vue 进阶系列教程将在本号持续发布,一起查漏补缺学个痛快!若您有遇到其它相关问题,非常欢迎在评论中留言讨论,达到帮助更多人的目的。若感本文对您有所帮助请点个赞吧! 2013年7月28日,尤雨溪第一次在 G…...
unity editor 编辑器 GUID localID LocalFileId 查找问题
//传入对象实例化ID 可以获取到 guid localid guid预设的ID localid 预设内的ID //这个方法有个问题如果在预设编辑器状态下 可能出现查不到 guid localid 原因可能 传入对象是是编辑状态下instanceid 并不是保存状态下的 UnityEditor.AssetDatabase.TryGetGUIDAndLocalF…...
MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...
《基于Apache Flink的流处理》笔记
思维导图 1-3 章 4-7章 8-11 章 参考资料 源码: https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...
UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...
【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统
目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索(基于物理空间 广播范围)2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...
力扣-35.搜索插入位置
题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...
虚拟电厂发展三大趋势:市场化、技术主导、车网互联
市场化:从政策驱动到多元盈利 政策全面赋能 2025年4月,国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》,首次明确虚拟电厂为“独立市场主体”,提出硬性目标:2027年全国调节能力≥2000万千瓦࿰…...
HubSpot推出与ChatGPT的深度集成引发兴奋与担忧
上周三,HubSpot宣布已构建与ChatGPT的深度集成,这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋,但同时也存在一些关于数据安全的担忧。 许多网络声音声称,这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...
【LeetCode】算法详解#6 ---除自身以外数组的乘积
1.题目介绍 给定一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O…...
保姆级【快数学会Android端“动画“】+ 实现补间动画和逐帧动画!!!
目录 补间动画 1.创建资源文件夹 2.设置文件夹类型 3.创建.xml文件 4.样式设计 5.动画设置 6.动画的实现 内容拓展 7.在原基础上继续添加.xml文件 8.xml代码编写 (1)rotate_anim (2)scale_anim (3)translate_anim 9.MainActivity.java代码汇总 10.效果展示 逐帧…...
五子棋测试用例
一.项目背景 1.1 项目简介 传统棋类文化的推广 五子棋是一种古老的棋类游戏,有着深厚的文化底蕴。通过将五子棋制作成网页游戏,可以让更多的人了解和接触到这一传统棋类文化。无论是国内还是国外的玩家,都可以通过网页五子棋感受到东方棋类…...
