当前位置: 首页 > 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…...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

C++:std::is_convertible

C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案

随着新能源汽车的快速普及&#xff0c;充电桩作为核心配套设施&#xff0c;其安全性与可靠性备受关注。然而&#xff0c;在高温、高负荷运行环境下&#xff0c;充电桩的散热问题与消防安全隐患日益凸显&#xff0c;成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

安卓基础(Java 和 Gradle 版本)

1. 设置项目的 JDK 版本 方法1&#xff1a;通过 Project Structure File → Project Structure... (或按 CtrlAltShiftS) 左侧选择 SDK Location 在 Gradle Settings 部分&#xff0c;设置 Gradle JDK 方法2&#xff1a;通过 Settings File → Settings... (或 CtrlAltS)…...