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

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

  • 原题链接:
  • 完成情况:
  • 解题思路:
      • 代码解释
        • 类级变量与初始化
        • 动态规划初始化
        • 递归函数 `dfs_maxProfit`
      • `Integer.MIN_VALUE / 5` 的作用
      • 总结
  • 参考代码:
    • _188买卖股票的最佳时机IV
  • 错误经验吸取

原题链接:

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

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/description/

完成情况:

在这里插入图片描述

解题思路:

代码解释

该代码实现了一个算法来计算在股票价格数组 prices 中最多进行 k 笔交易所能获得的最大利润。以下是对代码的详细解释:

类级变量与初始化
class Solution {private int[] prices;private int[][][] dp_maxProfit;public int maxProfit(int k, int[] prices) {this.prices = prices;int n = prices.length;dp_maxProfit = new int[n][k + 1][2];for (int i = 0; i < n; i++) {for (int j = 0; j <= k; j++) {Arrays.fill(dp_maxProfit[i][j], -1);}}return dfs_maxProfit(n - 1, k, 0);}
  • prices:存储股票价格数组。
  • dp_maxProfit:一个三维数组,保存到第 n 天进行了 t 次交易并且是否持有股票的最大利润。数组的维度为 [n][k+1][2],其中:
    • n:表示天数。
    • k+1:表示交易次数(包括 0 次交易)。
    • 2:表示是否持有股票(0 表示不持有,1 表示持有)。
动态规划初始化
        for (int i = 0; i < n; i++) {for (int j = 0; j <= k; j++) {Arrays.fill(dp_maxProfit[i][j], -1);}}
  • 使用 Arrays.fill 方法将 dp_maxProfit 三维数组的所有元素初始化为 -1,表示这些状态尚未计算。
递归函数 dfs_maxProfit
    private int dfs_maxProfit(int n, int t, int visited) {if (t < 0) return Integer.MIN_VALUE / 5; // 防止溢出if (n < 0) return visited == 1 ? Integer.MIN_VALUE / 5 : 0;if (dp_maxProfit[n][t][visited] != -1) return dp_maxProfit[n][t][visited];if (visited == 1) {return dp_maxProfit[n][t][visited] = Math.max(dfs_maxProfit(n - 1, t, 1), dfs_maxProfit(n - 1, t - 1, 0) - prices[n]);}return dp_maxProfit[n][t][visited] = Math.max(dfs_maxProfit(n - 1, t, 0), dfs_maxProfit(n - 1, t, 1) + prices[n]);}
}
  • dfs_maxProfit(n, t, visited):递归函数,用于计算到第 n 天进行了 t 次交易并且是否持有股票的最大利润。

    • 如果 t < 0:返回一个极小值 Integer.MIN_VALUE / 5。这用于防止溢出并确保不可能的状态不会影响结果。
    • 如果 n < 0:当天数已经小于 0,检查是否持有股票。如果持有股票,返回一个极小值 Integer.MIN_VALUE / 5。否则返回 0,表示没有任何交易利润。
    • 如果 dp_maxProfit[n][t][visited] != -1:直接返回预计算的结果,避免重复计算。
  • 递归逻辑:

    • 如果 visited == 1(当前持有股票),选择两种状态中的最大值:
      • 保持持有股票状态:dfs_maxProfit(n - 1, t, 1)
      • 卖出股票:dfs_maxProfit(n - 1, t - 1, 0) - prices[n]
    • 如果 visited == 0(当前不持有股票),选择两种状态中的最大值:
      • 保持不持有股票状态:dfs_maxProfit(n - 1, t, 0)
      • 买入股票:dfs_maxProfit(n - 1, t, 1) + prices[n]

Integer.MIN_VALUE / 5 的作用

  • return Integer.MIN_VALUE / 5; // 防止溢出

该语句用于在递归过程中避免溢出。具体原因如下:

  • Integer.MIN_VALUE 是 Java 中整数的最小值,即 -2^31。如果直接使用 Integer.MIN_VALUE 作为返回值,在某些计算中可能会导致溢出,变成正数。
  • Integer.MIN_VALUE 除以 5,仍然是一个很小的负数,但不至于达到溢出风险。这样可以确保逻辑处理时不会因为极值导致错误。

总结

这段代码使用了动态规划和递归相结合的方法,通过三维数组 dp_maxProfit 来记录不同状态下的最大利润,避免了重复计算,确保在最多进行 k 次交易的情况下,能计算出最大可能利润。

参考代码:

_188买卖股票的最佳时机IV

package leetcode板块;import java.util.Arrays;public class _188买卖股票的最佳时机IV {private int [] prices;private int [][][] dp_maxProfit;  // 扩大维度/**** @param k* @param prices* @return*/public int maxProfit(int k, int[] prices) {//设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说,你最多可以买 k 次,卖 k 次。// TODO 类似于刚才的 -> 123买卖股票的最佳时机III ???   构造k维数组,去求dp的K,k与k+1之间通过迭代去计算k维的利润集合。this.prices = prices;int n = prices.length;dp_maxProfit = new int[n][k+1][2];  //  n个数组值 ,k+1去记录作为第几笔交易的"最大利润" ,2用于去记录当前操作下是否访问过该号位元素for (int i = 0;i<n;i++){for (int j = 0;j<=k;++j){Arrays.fill(dp_maxProfit[i][j],-1); //memories[i][j]的下一级全部标为 -1}}return dfs_maxProfit(n-1,k,0);}/**** @param n :numbers* @param t :transaction* @param visited* @return*/private int dfs_maxProfit(int n, int t, int visited) {if (t < 0)    return  Integer.MIN_VALUE / 5; // 防止溢出if (n < 0)    return  visited == 1 ? Integer.MIN_VALUE / 5 : 0;if (dp_maxProfit[n][t][visited] != -1)  return dp_maxProfit[n][t][visited];if (visited ==  1){return dp_maxProfit[n][t][visited] = Math.max(dfs_maxProfit(n-1,t,1),dfs_maxProfit(n-1,t-1,0) - prices[n]);}return dp_maxProfit[n][t][visited] = Math.max(dfs_maxProfit(n-1,t,0),dfs_maxProfit(n-1,t,1)+prices[n]);}

错误经验吸取

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

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

相关文章

全面升级,票据识别新纪元:合合信息TextIn多票识别2.0

票据识别 - 自动化业务的守门员 发票、票据识别&#xff0c;是OCR技术和RPA、CMS系统结合的一个典型场景&#xff0c;从覆盖率、覆盖面的角度来说&#xff0c;应该也是结合得最成功的场景之一。 产品简介 国内通用票据识别V2.0&#xff08;简称“多票识别2.0”&#xff09;是…

Java 集合框架详谈及代码分析(Iterable->Collection->List、Set->各接口实现类、Map->各接口实现类)

目录 Java 集合框架详谈及代码分析&#xff08;Iterable->Collection->List、Set->各接口实现类、Map->各接口实现类&#xff09;1、集合概述1-1&#xff1a;Java 集合概述1-2&#xff1a;List、Set、Map 三者的区别&#xff1f;1-3&#xff1a;集合框架底层数据结…

SM4 国密——加密,解密

SM4 国密的使用 前言——引用管理包SM4解密——ECB模式SM4加密——ECB模式SM4解密——CBC模式SM4加密——CBC模式SM4工具类SM4主体类SM4实体类 前言——引用管理包 引用NuGet管理包BouncyCastle.Crypto SM4解密——ECB模式 public string CiphertextParsing(string json) {tr…

四十八、openlayers地图调色总结——锐化、模糊、浮雕滤镜,调整地图色相、饱和度、亮度

这篇是对滤镜的总结&#xff0c;方便工作中直接使用。 想要调整图层的颜色&#xff0c;有两种方法。 方法一&#xff1a; 加载图层时使用tileLoadFunction函数拿到context添加canvas滤镜效果。 this.imagery new TileLayer({source: new XYZ({url: "https://server.arc…

android串口助手apk下载 源码 演示 支持android 4-14及以上

android串口助手apk下载 1、自动获取串口列表 2、打开串口就开始接收 3、收发 字符或16进制 4、默认发送at\r\n 5、android串口助手apk 支持android 4-14 &#xff08;Google seral port 太老&#xff09; 源码找我 需要 用adb root 再setenforce 0进入SELinux 模式 才有权限…

关于docker无法正常下载镜像的问题

文章目录 之前还可以正常下载镜像&#xff0c;但是一段时间之后就无法下载了&#xff0c;猜测可能是政治原因&#xff0c;无法连接到国外服务器&#xff0c;所以我设置了阿里云的镜像加速器。 配置方法如下&#xff1a; 前往阿里云&#xff08;https://help.aliyun.com/zh/acr/…

理解HTTP请求格式

HTTP概念 HTTP全称HyperTextTransfer Protocol(超文本传输协议)是一种用于分布式、协作式和超媒体信息系统的应用层协议&#xff1b;HTTP是一个客户端&#xff08;用户&#xff09;和服务端&#xff08;网站&#xff09;之间请求和响应的标准。 HTTP 协议是以 ASCII 码传输&…

Ethena 更新代币经济学,逼着空投用户作长期 Hodler?

撰文&#xff1a;Yangz&#xff0c;Techub News 本文来源香港Web3媒体Techub News 6 月 18 日&#xff0c;Ethena 更新代币经济学&#xff0c;计划在 Ethena 生态和即将推出的 Ethena Chain 中引入通用再质押机制&#xff0c;并对任何通过空投获得 ENA 的用户实施「锁定」要求…

【黑马TS】学习资料Day4

五、在 React 中使用 TypeScript 现在&#xff0c;我们已经掌握了 TS 中基础类型、高级类型的使用了。但是&#xff0c;如果要在前端项目开发中使用 TS&#xff0c;还需要掌握 React、Vue、Angular 等这些库或框架中提供的 API 的类型&#xff0c;以及在 TS 中是如何使用的。 …

基于Redis提高查询性能(保持数据一致性)

Redis实战篇 | Kyles Blog (cyborg2077.github.io) 目录 背景 商户查询缓存(根据ID查询&#xff09; 根据店铺类型查询&#xff08;List型&#xff09; 缓存更新策略&#xff08;保证数据一致性&#xff09; 案例&#xff08;利用缓存更新策略&#xff09; 背景 起初客户端…

Hadoop3:MapReduce中的Shuffle机制

一、流程图 Shuffle是Map方法之后&#xff0c;Reduce方法之前的数据处理过程称。 二、图解说明 1、数据流向 map方法中context.write(outK, outV);开始&#xff0c;写入环形缓冲区&#xff0c;再进行分区排序&#xff0c;写到磁盘 reduce方法拉取磁盘上的数据&#xff0c;…

JavaSE 面向对象程序设计高级 方法引用 2024详解

在编程中&#xff0c;方法引用&#xff08;Method Reference&#xff09;是一种技术&#xff0c;它让你能够直接引用一个现有的函数或方法&#xff0c;而无需通过对象实例来调用。这种方法在函数式编程和高阶函数中非常有用&#xff0c;因为它提供了简洁的方式来传递函数行为&a…

【归档】maven的使用

学习自波波酱老师SSM企业级框架最全教学视频 maven篇 maven的设置 <?xml version"1.0" encoding"UTF-8"?> <settings xmlns"http://maven.apache.org/SETTINGS/1.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance&qu…

【ARMv8/ARMv9 硬件加速系列 3 -- SVE 硬件加速向量运算 1】

文章目录 SVE 使用介绍SVE 特点SVE2 特点 SVE 寄存器扩展的向量寄存器可扩展的谓词寄存器.d 与 .b 后缀的区别举例介绍使用 .d 后缀进行64位元素操作使用 .b 后缀进行8位元素操作 ptrue 指令小结 FFR 寄存器 SVE 使用介绍 前面文章:【ARMv8/ARMv9 硬件加速系列 1 – SVE | NEO…

AttributeError: module ‘numpy‘ has no attribute ‘int‘解决方案

大家好,我是爱编程的喵喵。双985硕士毕业,现担任全栈工程师一职,热衷于将数据思维应用到工作与生活中。从事机器学习以及相关的前后端开发工作。曾在阿里云、科大讯飞、CCF等比赛获得多次Top名次。现为CSDN博客专家、人工智能领域优质创作者。喜欢通过博客创作的方式对所学的…

C++ Windows Hook使用

GitHub - microsoft/Detours: Detours is a software package for monitoring and instrumenting API calls on Windows. It is distributed in source code form. /*挂载钩子 setdll /d:C:\Users\g\source\repos\LotTest\Release\lotDll.dll C:\Users\g\source\repos\LotTest…

React 通信:深层传递(Props、Context、Children Jsx)

在之前的文章 探讨&#xff1a;围绕 props 阐述 React 通信 中总结了关于“父子”组件传值&#xff0c;但是当需要在组件树中深层传递参数以及需要在组件间复用相同的参数时&#xff0c;传递 props 就会变得很麻烦。 实际案例&#xff1a; 下述展示有两种状态&#xff1a;① 详…

【无线传感网】LEACH路由算法

1、LEACH路由算法简介 LEACH协议,全称是“低功耗自适应集簇分层型协议” (Low Energy Adaptive Clustering Hierarchy),是一种无线传感器网络路由协议。基于LEACH协议的算法,称为LEACH算法。 2、LEACH路由算法的基本思想 LEACH路由协议与以往的路由协议的不同之处在于其改变…

<Rust><iced>基于rust使用iced构建GUI实例:如何将svg格式转为ico格式图片?

前言 本专栏是Rust实例应用。 环境配置 平台:windows 软件:vscode 语言:rust 库:iced、iced_aw 概述 本文是专栏第4篇实例,依旧是一个图像格式转换程序,基于rust的svg库resvg、图像处理库image以及文件处理库rfd。 流程是先用resvg获取svg图片的数据并将其转为png数据…

嵌入式实验---实验一 通用GPIO实验

一、实验目的 1、掌握STM32F103 GPIO程序设计流程&#xff1b; 2、熟悉STM32固件库的基本使用。 二、实验原理 1、通过按键实现&#xff1a;按键按下&#xff0c;LED点亮&#xff1b;按键释放&#xff0c;LED熄灭。 三、实验设备和器材 电脑、Keil uVision5软件、Proteus…