leetcode-买卖股票问题

309. 买卖股票的最佳时机含冷冻期 - 力扣（LeetCode）

        动态规划解题思路：

1、暴力递归（难点如何定义递归函数）

2、记忆化搜索-傻缓存法（根据暴力递归可变参数确定缓存数组维度）

3、严格表结构依赖的动态规划

4、进一步优化（斜率优化、空间优化），非必须

一、分析：假设[0,index-1]之前的最大利润已经知道，现在计算到了index位置的最大利润。根据题意，到index位置后可能有三种状态，买入、卖出、冷冻。所以递归函数如下。

    public int maxProfit(int[] prices) {return p(prices,0,0);}// 0-买入 1-卖出 2-冷冻// 递归函数表示 从index位置到prices.length-1位置的最大利润public int p(int[] prices, int index, int state) {if (index == prices.length) {return 0;}int res = 0;if (state == 0) {// 买入 当前indexint p1 = -prices[index] + p(prices, index + 1, 1);// 不买当前indexint p2 = p(prices, index + 1, 0);return Math.max(p1, p2);} else if (state == 1) {// 卖当前indexint p1 = prices[index] + p(prices, index + 1, 2);// 不卖当前indexint p2 = p(prices, index + 1, 1);return Math.max(p1, p2);} else {//冷冻return p(prices, index + 1, 0);}}

二、我们直接看表依赖，略过傻缓存法。根据暴力递归函数分析，有两个可变参数，所以申请一个二维数组即可，看递归的base case初始化dp数组；看依赖关系index位置只依赖于index+1位置的元素，所以填数组的顺序为index倒序。返回值看递归调用的参数值是什么，就返回dp数组哪个位置的值。

    public int maxProfit2(int[] prices) {int N = prices.length;int[][] dp = new int[N + 1][3];for (int index = N - 1; index >= 0; index--) {dp[index][2] = dp[index + 1][0];dp[index][1] = Math.max(prices[index] + dp[index + 1][2], dp[index + 1][1]);dp[index][0] = Math.max(-prices[index] + dp[index][1], dp[index + 1][0]);}return dp[0][0];}

三、我们分析知道index位置只依赖于index+1位置的元素，也就是说index行的数据只依赖index+1行的数据，所以可以只用一个一维数组，循环更新即可。

    public int maxProfit(int[] prices) {int N = prices.length;//空间优化int[] dp = new int[3];for (int index = N - 1; index >= 0; index--) {int temp = dp[0];dp[0] = Math.max(-prices[index] + dp[1], dp[0]);dp[1] = Math.max(prices[index] + dp[2], dp[1]);dp[2] = temp;}return dp[0];}

 714. 买卖股票的最佳时机含手续费 - 力扣（LeetCode）

        该题的解法和上题类似，只是多了手续费，少了冷冻期。

一、暴力递归

    int f=0;public int maxProfit1(int[] prices, int fee) {f = fee;return p(prices, 0, 0);}// 0-买入 1-卖出public int p(int[] prices, int index, int state) {if (index == prices.length) {return 0;}int res = 0;if (state == 0) {// 买入 当前indexint p1 = -prices[index] - f + p(prices, index + 1, 1);// 不买当前indexint p2 = p(prices, index + 1, 0);return Math.max(p1, p2);} else {// 可以卖int p1 = prices[index] + p(prices, index + 1, 0);int p2 = p(prices, index + 1, 1);return Math.max(p1, p2);}}

二、表结构动态规划

    public int maxProfit2(int[] prices, int fee) {int N = prices.length;int[][] dp = new int[N + 1][2];for (int index = N - 1; index >= 0; index--) {dp[index][1] = Math.max(prices[index] + dp[index + 1][0], dp[index + 1][1]);dp[index][0] = Math.max(-prices[index] - fee + dp[index][1], dp[index + 1][0]);}return dp[0][0];}

三、空间优化

    public int maxProfit4(int[] prices, int fee) {int N = prices.length;// 空间优化int buy=0,sell=0;for (int index = N - 1; index >= 0; index--) {int temp = buy;buy = Math.max(-prices[index] - fee + sell, buy);sell = Math.max(prices[index] + temp, sell);}return buy;}public int maxProfit3(int[] prices, int fee) {int N = prices.length;// 空间优化int[] dp = new int[2];for (int index = N - 1; index >= 0; index--) {int temp = dp[0];dp[0] = Math.max(-prices[index] - fee + dp[1], dp[0]);dp[1] = Math.max(prices[index] + temp, dp[1]);}return dp[0];}

123. 买卖股票的最佳时机 III - 力扣（LeetCode）

        该题的差异在于：没有冷冻期、没有手续费，但是限制了交易次数，也就是说我们的可变参数需要再加一个交易次数即可。

一、暴力递归

    public int maxProfit1(int[] prices) {return p(prices, 0, 0, 0);}public int p(int[] prices, int index, int state, int count) {if (index == prices.length) {return 0;}if (count == 2) {return 0;}int p1 = 0, p2 = 0;if (state == 0) {// buyp1 = -prices[index] + p(prices, index + 1, 1, count);p2 = p(prices, index + 1, 0, count);} else {// 卖出p1 = prices[index] + p(prices, index + 1, 0, count + 1);p2 = p(prices, index + 1, 1, count);}return Math.max(p1, p2);}

二、动态规划

    public int maxProfit2(int[] prices) {int N = prices.length;// state countint[][][] dp = new int[N + 1][2][3];for (int index = N - 1; index >= 0; index--) {for (int count = 1; count >= 0; count--) {dp[index][0][count] = Math.max(-prices[index] + dp[index + 1][1][count], dp[index + 1][0][count]);dp[index][1][count] = Math.max(prices[index] + (count + 1 == 2 ? 0 : dp[index + 1][0][count + 1]),dp[index + 1][1][count]);}}return dp[0][0][0];}

三、空间优化（从下至上逐步优化到最优的maxProfit5）

    public int maxProfit5(int[] prices) {int N = prices.length;// state countint buy1 = 0;int sell1 = 0;int buy2 = 0;int sell2 = 0;for (int index = N - 1; index >= 0; index--) {buy2 = Math.max(-prices[index] + sell2, buy2);sell2 = Math.max(prices[index], sell2);buy1 = Math.max(-prices[index] + sell1, buy1);sell1 = Math.max(prices[index] + buy2, sell1);}return buy1;}public int maxProfit4(int[] prices) {int N = prices.length;// state count dp[0][0] 买1 dp[0][1]买2 dp[1][0]卖1 dp[1][1] 卖2int[][] dp = new int[2][3];for (int index = N - 1; index >= 0; index--) {dp[0][1] = Math.max(-prices[index] + dp[1][1], dp[0][1]);dp[1][1] = Math.max(prices[index], dp[1][1]);dp[0][0] = Math.max(-prices[index] + dp[1][0], dp[0][0]);dp[1][0] = Math.max(prices[index] + dp[0][1], dp[1][0]);}return dp[0][0];}public int maxProfit3(int[] prices) {int N = prices.length;// state countint[][] dp = new int[2][3];for (int index = N - 1; index >= 0; index--) {for (int count = 1; count >= 0; count--) {dp[0][count] = Math.max(-prices[index] + dp[1][count], dp[0][count]);dp[1][count] = Math.max(prices[index] + (count + 1 == 2 ? 0 : dp[0][count + 1]), dp[1][count]);}}return dp[0][0];}

188. 买卖股票的最佳时机 IV - 力扣（LeetCode）

        该题解法和上题类似，只是交易次数为k。

一、暴力递归

    int times=0;public int maxProfit1(int k, int[] prices) {times = k;return p(prices, 0, 0, 0);}public int p(int[] prices, int index, int state, int count) {if (index == prices.length) {return 0;}if (count == times) {return 0;}int p1 = 0, p2 = 0;if (state == 0) {// buyp1 = -prices[index] + p(prices, index + 1, 1, count);p2 = p(prices, index + 1, 0, count);} else {// 卖出p1 = prices[index] + p(prices, index + 1, 0, count + 1);p2 = p(prices, index + 1, 1, count);}return Math.max(p1, p2);}

二、动态规划

    public int maxProfit(int k, int[] prices) {int N = prices.length;// state countint[][] dp = new int[2][k];for (int index = N - 1; index >= 0; index--) {for (int count = k - 1; count >= 0; count--) {dp[0][count] = Math.max(-prices[index] + dp[1][count], dp[0][count]);dp[1][count] = Math.max(prices[index] + (count + 1 == k ? 0 : dp[0][count + 1]), dp[1][count]);}}return dp[0][0];}

        该题就没啥可空间优化，所以到这就结束了。我觉得这个代码是最好理解的。

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

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

相关文章

蓝桥杯训练—斐波那契数列

蓝桥杯训练—斐波那契数列

文章目录 一、题目二、解析三、代码 一、题目 求100以内的斐波那契数列 斐波那契数列（Fibonacci sequence），又称黄金分割数列 ，因数学家莱昂纳多斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入&…
阅读更多...
nginx 配置防爬虫

nginx 配置防爬虫

今天早上查看服务器，发现昨天发布的一个在线解析充电桩协议的网页工具有大量的访问记录，应该是爬虫在爬api接口数据。该工具api接口后台用的是python写的，和大多数项目一样也采用nginx反向代理，由于采用nginx，可以利用…
阅读更多...
Mockito+PowerMock+Junit单元测试

Mockito+PowerMock+Junit单元测试

一、单元测试用途 1、日常开发团队要求规范，需要对开发需求代码进行单元测试并要求行覆盖率达到要求，DevOps流水线也会开设相关门禁阀值阻断代码提交，一般新增代码行覆盖率80%左右。 二、Mock测试介绍 1、Mock是为了解决不同的单元之间由于…
阅读更多...
左神算法基础提升--3

左神算法基础提升--3

文章目录 Manacher 算法经典算法Manacher算法原理 单调栈或单调队列 Manacher 算法 经典算法 在每学习Manacher算法之前我们可能会使用一种比较经典暴力的算法：遍历str字符串，将字符串中的每个字符作为对称点，向两边扩散找到回文字段&#x…
阅读更多...
Android系统开发（八）：从麦克风到扬声器，音频HAL框架的奇妙之旅

Android系统开发（八）：从麦克风到扬声器，音频HAL框架的奇妙之旅

引言：音浪太强，我稳如老 HAL！ 如果有一天你的耳机里传来的不是《咱们屯里人》，而是金属碰撞般的杂音，那你可能已经感受到了 Android 音频硬件抽象层 (HAL) 出问题的后果！在 Android 音频架构中&#xff0c…
阅读更多...
OA-CNN：用于 3D 语义分割的全自适应稀疏 CNN

OA-CNN：用于 3D 语义分割的全自适应稀疏 CNN

大家读完觉得有帮助记得及时关注和点赞！！！ 1介绍 2相关工作 基于点的学习。 基于 CNN 的学习。 动态卷积。 3全能自适应 3D 稀疏 CNN 3.1空间适应性感受野 赋予动机。 体素网格。 金字塔网格分区。 Adaptive 聚合器。 3.2自适应关…
阅读更多...
聊聊如何实现Android 放大镜效果

聊聊如何实现Android 放大镜效果

一、前言 很久没有更新Android 原生技术内容了，前些年一直在做跨端方向开发，最近换工作用重新回到原生技术，又回到了熟悉但有些生疏的环境，真是感慨万分。 近期也是因为准备做地图交互相关的需求，功能非常复杂&#x…
阅读更多...
Linux 操作二：文件映射与文件状态

Linux 操作二：文件映射与文件状态

Linux 操作二：文件映射与文件状态查询 文件映射 ​ mmap是一种内存映射文件的方法，即将一个文件或者其它对象映射到进程的地址空间，实现文件磁盘地址和进程虚拟地址空间中一段虚拟地址的一一对映关系。实现这样的映射关系后，进程…
阅读更多...
论文阅读：CosAE Learnable Fourier Series for Image Restoration

论文阅读：CosAE Learnable Fourier Series for Image Restoration

这是 2024 NeurIPS 上发表的一篇文章，介绍了一种新型的基于傅里叶级数的通用编码器。 Abstract 本文介绍了余弦自动编码器（Cosine Autoencoder, CosAE），这是一种新颖的通用自动编码器，它将经典傅里叶级数与前馈神经网…
阅读更多...
数据库服务体系结构

数据库服务体系结构

1. 数据库服务应用配置 服务进行配置有什么作用？ 实现服务运行启动 实现某些功能 应用配置有三种方式？ 利用编译安装进行配置 编写配置文件信息 ,.默认的配置文件: /etc/my.cnf 利用启动命令参数配置信息，mysqld_safe --skip-grant-tables --…
阅读更多...
Armv8/Armv9架构从入门到精通-介绍

Armv8/Armv9架构从入门到精通-介绍

CSDN学院课程连接：https://edu.csdn.net/course/detail/39573 1 讲师介绍 拥有 12 年手机安全、汽车安全、芯片安全开发经验，擅长 Trustzone/TEE/ 安全的设计与开发，对 ARM 架构的安全领域有着深入的研究和丰富的实践经验，能够…
阅读更多...
【Web】2025西湖论剑·中国杭州网络安全安全技能大赛题解(全)

【Web】2025西湖论剑·中国杭州网络安全安全技能大赛题解(全)

目录 Rank-l Rank-U sqli or not Rank-l username存在报错回显，发现可以打SSTI 本地起一个服务，折半查找fuzz黑名单，不断扔给fenjing去迭代改payload from flask import Flask, request, render_template_stringapp Flask(__name__)app…
阅读更多...
2025.1.17——三、SQLi regexp正则表达式|

2025.1.17——三、SQLi regexp正则表达式|

题目来源：buuctf [NCTF2019]SQLi1 目录 一、打开靶机，整理信息 二、解题思路 step 1：正常注入 step 2：弄清关键字黑名单 1.目录扫描 2.bp爆破 step 3：根据过滤名单构造payload step 4：regexp正则注…
阅读更多...
使用 Java 开发 Android 应用：Kotlin 与 Java 的混合编程

使用 Java 开发 Android 应用：Kotlin 与 Java 的混合编程

使用 Java 开发 Android 应用：Kotlin 与 Java 的混合编程 在开发 Android 应用程序时，我们通常可以选择使用 Java 或 Kotlin 作为主要的编程语言。然而，有些开发者可能会想要在同一个项目中同时使用这两种语言，这就是所谓的混合编…
阅读更多...
【机器学习实战中阶】音乐流派分类-自动化分类不同音乐风格

【机器学习实战中阶】音乐流派分类-自动化分类不同音乐风格

音乐流派分类 – 自动化分类不同音乐风格 在本教程中，我们将开发一个深度学习项目，用于自动化地从音频文件中分类不同的音乐流派。我们将使用音频文件的频率域和时间域低级特征来分类这些音频文件。 对于这个项目，我们需要一个具有相似大小和相似频率范围的音频曲目数据集…
阅读更多...
【C++】面试题整理（未完待续）

【C++】面试题整理（未完待续）

【C】面试题整理 文章目录 一、概述二、C基础2.1 - 指针在 32 位和 64 位系统中的长度2.2 - 数组和指针2.3 - 结构体对齐补齐2.4 - 头文件包含2.5 - 堆和栈的区别2.6 - 宏函数比较两个数值的大小2.7 - 冒泡排序2.8 - 菱形继承的内存布局2.9 - 继承重写2.10 - 如何禁止类在栈上分…
阅读更多...
简历_使用 Redis 解决集群模式下的 Session 共享问题，使用拦截器实现用户的登录，校验和权限刷新以及对单位时间内请求频繁的用户IP地址进行限流。

简历_使用 Redis 解决集群模式下的 Session 共享问题，使用拦截器实现用户的登录，校验和权限刷新以及对单位时间内请求频繁的用户IP地址进行限流。

系列博客目录 文章目录 系列博客目录1.使用 Redis 解决集群模式下的 Session 共享问题集群的session共享问题总结 2.使用拦截器实现用户的登录，校验和权限刷新3.对单位时间内请求频繁的用户IP地址进行限流。实现思路步骤：1. 添加 Redis 依赖2. 配置 Redi…
阅读更多...
构建安全防线：基于视频AI的煤矿管理系统架构创新成果展示

构建安全防线：基于视频AI的煤矿管理系统架构创新成果展示

前言 本文我将介绍一款AI产品的成果展示——“基于视频AI识别技术的煤矿安全生产管理系统”。这款产品是目前我在创业阶段和几位矿业大学的博士共同从架构设计、开发到交付的全过程中首次在博客频道发布, 我之前一直想写但没有机会来整理这套系统的架构, 因此我也特别感谢CSDN平…
阅读更多...
浅谈计算机网络04 | 现代网络需求与技术支撑

浅谈计算机网络04 | 现代网络需求与技术支撑

现代网络需求与技术支撑 一、网络和因特网流量的类型剖析1.1 弹性流量的自适应特征1.2 非弹性流量的刚性特征1.3 实时流量特性 二、特定领域的网络需求解析2.1 大数据环境下的网络需求分析2.2 云计算环境下的网络需求分析2.3 移动数据环境下的网络需求分析 三、QoS和QoE&#x…
阅读更多...
麒麟操作系统服务架构保姆级教程（十一）https配置

麒麟操作系统服务架构保姆级教程（十一）https配置

如果你想拥有你从未拥有过的东西，那么你必须去做你从未做过的事情 在运维工作中，加密和安全的作用是十分重要的，如果仅仅用http协议来对外展示我们的网站，过一段时间就会发现网站首页被人奇奇怪怪的篡改了，本来好好的博…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023