「动态规划」买卖股票的最佳时机，如何处理多笔交易？

2024-06-15 05:12
文章标签 动态 规划 股票 处理 最佳时机 买卖 交易 多笔

本文主要是介绍「动态规划」买卖股票的最佳时机，如何处理多笔交易？，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

188. 买卖股票的最佳时机 IVicon-default.png?t=N7T8https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/description/

给你一个整数数组prices和一个整数k，其中prices[i]是某支给定的股票在第i天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成k笔交易。也就是说，你最多可以买k次，卖k次。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

  1. 输入：k = 2，prices = [2,4,1]，输出：2，解释：在第1天（股票价格 = 2）的时候买入，在第2天（股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4 - 2 = 2。
  2. 输入：k = 2，prices = [3,2,6,5,0,3]，输出：7，解释：在第2天（股票价格 = 2）的时候买入，在第3天（股票价格 = 6）的时候卖出，这笔交易所能获得利润 = 6 - 2 = 4。随后，在第5天（股票价格 = 0）的时候买入，在第6天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3 - 0 = 3。

提示：1 <= k <= 100，1 <= prices.length <= 1000，0 <= prices[i] <= 1000。

我们用动态规划的思想来解决这个问题。

确定状态表示：根据经验和题目要求，我们把状态细分为：

  • 我们用f[i][j]表示：在第i天结束时，处于买入状态下，总共交易j次，此时的最大利润。
  • 我们用g[i][j]表示：在第i天结束时，处于卖出状态下，总共交易j次，此时的最大利润。

解释一下上面出现的名词。如果我们手里有股票，我们称当前处于买入状态下；如果我们手里没有股票，我们称当前处于卖出状态下。一次完整的买入持有到卖出称为一笔交易，也就是说，一开始的交易次数为0，在每次卖出时交易次数加1。每次买入股票会让利润减少股票在当天的价格，卖出股票会让利润增加股票在当天的价格。在状态表示中，f和g分别表示买入和卖出状态，i表示天数，j表示交易次数，f[i][j]和g[i][j]表示最大利润。

推导状态转移方程：我们需要考虑最近的一步，即第i - 1天的状态和交易次数。

首先考虑f[i][j]，即在第i天结束时处于买入状态下，且交易了j次。

  • 如果在第i - 1天结束时，处于买入状态下，且交易了j次，此时的利润是f[i - 1][j]，那么只需要在第i天什么都不做，在第i天结束时，依然处于买入状态下，且交易了j次，利润不变，依然是f[i - 1][j]。
  • 如果在第i - 1天结束时，处于卖出状态下，且交易了j次，此时的利润是g[i - 1][j]，那么只需要在第i天买入股票，在第i天结束时，就会处于买入状态下，且交易了j次，利润减少股票在第i天的价格，即g[i - 1][j] - prices[i]。

由于f[i][j]表示最大利润，所以取上面2种情况的较大值，即f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i])。

接着考虑g[i][j]，即在第i天结束时处于卖出状态下，且交易了j次。

  • 如果在第i - 1天结束时，处于买入状态下，且交易了j - 1次，此时的利润是f[i - 1][j - 1]，那么只需要在第i天卖出股票，在第i天结束时，就会处于卖出状态下，交易次数加1，即交易了j次，利润增加股票在第i天的价格，即f[i - 1][j - 1] + prices[i]。
  • 如果在第i - 1天结束时，处于卖出状态下，且交易了j次，此时的利润是g[i - 1][j]，那么只需要在第i天什么都不做，在第i天结束时，依然处于卖出状态下，且交易了j次，利润不变，依然是g[i - 1][j]。

由于g[i][j]表示最大利润，所以取上面2种情况的较大值，即g[i][j] = max(f[i - 1][j - 1] + prices[i], g[i - 1][j])。

综上所述：f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i])，g[i][j] = max(f[i - 1][j - 1] + prices[i], g[i - 1][j])。

初始化：根据状态转移方程，

  • 计算f[i][j]时，当i = 0时会越界。
  • 计算g[i][j]时，当i = 0或j = 0时会越界。

所以，我们要初始化相应的位置。容易想到：

  • f[0][0]表示在第0天结束时，处于买入状态下，此时的最大利润。一开始利润是0，在第0天买入股票，显然f[0][0] = -prices[0]。
  • g[0][0]表示在第0天结束时，处于卖出状态下，此时的最大利润。一开始利润是0，在第0天什么都不做，显然g[0][0] = 0。

接着考虑f[0][j]，其中j > 0。j > 0说明交易次数至少是1次，也就是说在第0天一定做出了买入并且立刻卖出股票的操作。然而这种操作是没有意义的，因为浪费了交易次数，并不会增加最大利润。观察状态转移方程，发现不管是f[i][j]还是g[i][j]，最终都是对2个值求max。要想不影响到计算结果，我们要对f[0][j]，其中j > 0的位置的值都初始化为-∞。同理g[0][j]，其中j > 0的位置的值也要初始化为-∞。考虑到状态转移方程中，有g[i - 1][j] - prices[i]这样有溢出风险的计算，所以不能简单地用INT_MIN表示-∞，而要用-0x3f3f3f3f。

再考虑g[i][0]，其中i > 0。观察状态转移方程：g[i][j] = max(f[i - 1][j - 1] + prices[i], g[i - 1][j])。为什么g[i][0]，其中i > 0的位置会越界呢？因为方程中含有f[i - 1][j - 1]，当j = 0时，j - 1 = -1，不存在交易次数为-1的情况。所以，我们需要判断一下，当j - 1 = -1时，这种情况不存在，相当于求max的2项中，前一项不存在，那么就只剩下后一项，即g[i - 1][j]，即此时g[i][j] = g[i - 1][j]。只有当j - 1 >= 0时，求max的2项都有意义，此时才计算g[i][j] = max(f[i - 1][j - 1] + prices[i], g[i - 1][j])。也就是说，先让g[i][j] = g[i - 1][j]，接着判断j - 1是否大于-1，即j是否大于0，如果判断成立，再让g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i])。

综上所述：初始化需要注意以下几点：f[0][0] = -prices[0]；g[0][0] = 0；f[0][j] = g[0][j] = -0x3f3f3f3f，其中j > 0；当i > 0时，先让g[i][j] = g[i - 1][j]，接着判断j - 1是否大于-1，即j是否大于0，如果判断成立，再让g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i])。只需做到以上几点，就不会越界。

填表顺序：观察状态转移方程，显然我们要沿着i和j增大的方向同时填f表和g表。

返回值：假设总共有n天，最多完成k笔交易。对于第i天，i的范围是[0, n - 1]。根据题目要求，我们要返回的是最后一天结束后的最大利润，即第n - 1天结束后的最大利润。可以确定，如果要求最大利润，第n - 1天结束后一定要处于卖出状态下，否则在第n - 1天卖出股票可以获得更多利润。另外，并不确定第n - 1天结束后的交易次数。根据状态表示，我们要返回的是g[n - 1][j]的最大值，其中j的范围是[0, k]。

细节问题：由于i的范围是[0, n - 1]，j的范围是[0, k]，所以f表和g表的规模都是n x (k + 1)。另外，交易次数不会超过天数的一半，所以要先计算k = min(k, n / 2)。

时间复杂度：O(N^2)，空间复杂度：O(N^2)。最坏情况是k刚好是n的一半。

class Solution {
public:int maxProfit(int k, vector<int>& prices) {const int INF = 0x3f3f3f3f;int n = prices.size();// 交易次数不会超过天数的一半k = min(k, n / 2);// 创建dp表vector<vector<int>> f(n, vector<int>(k + 1, -INF));auto g = f;// 初始化f[0][0] = -prices[0];g[0][0] = 0;// 填表for (int i = 1; i < n; i++) {for (int j = 0; j <= k; j++) {f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);g[i][j] = g[i - 1][j];if (j > 0) {g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);}}}// 返回结果return *max_element(g[n - 1].begin(), g[n - 1].end());}
};

123. 买卖股票的最佳时机 IIIicon-default.png?t=N7T8https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/

给定一个数组，它的第i个元素是一支给定的股票在第i天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

  1. 输入：prices = [3,3,5,0,0,3,1,4]，输出：6，解释：在第4天（股票价格 = 0）的时候买入，在第6天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3 - 0 = 3 。随后，在第7天（股票价格 = 1）的时候买入，在第8天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4 - 1 = 3。
  2. 输入：prices = [1,2,3,4,5]，输出：4，解释：在第1天（股票价格 = 1）的时候买入，在第5天 （股票价格 = 5）的时候卖出，这笔交易所能获得利润 = 5 - 1 = 4。注意你不能在第1天和第2天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
  3. 输入：prices = [7,6,4,3,1]，输出：0，解释：在这个情况下，没有交易完成，所以最大利润为0。
  4. 输入：prices = [1]，输出：0

提示：1 <= prices.length <= 10^5，0 <= prices[i] <= 10^5。

这道题是上道题在k = 2时的特殊情况，我们只需要复用上道题的代码就行了。当然，感兴趣的话，你也可以用动态规划的思想来分析分析。

class Solution {
public:int maxProfit(vector<int>& prices) { return maxProfit(2, prices); }private:int maxProfit(int k, vector<int>& prices) {const int INF = 0x3f3f3f3f;int n = prices.size();// 交易次数不会超过天数的一半k = min(k, n / 2);// 创建dp表vector<vector<int>> f(n, vector<int>(k + 1, -INF));auto g = f;// 初始化f[0][0] = -prices[0];g[0][0] = 0;// 填表for (int i = 1; i < n; i++) {for (int j = 0; j <= k; j++) {f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);g[i][j] = g[i - 1][j];if (j > 0) {g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);}}}// 返回结果return *max_element(g[n - 1].begin(), g[n - 1].end());}
};

这篇关于「动态规划」买卖股票的最佳时机，如何处理多笔交易？的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1062513。

相关文章

捷瑞数字业绩波动性明显：关联交易不低，募资必要性遭质疑

捷瑞数字业绩波动性明显：关联交易不低，募资必要性遭质疑

《港湾商业观察》施子夫 5月22日，山东捷瑞数字科技股份有限公司（以下简称，捷瑞数字）及保荐机构国新证券披露第三轮问询的回复，继续推进北交所上市进程。 从2023年6月递表开始，监管层已下发三轮审核问询函，关注到捷瑞数字存在同业竞争、关联交易、募资合理性、期后业绩波动等焦点问题。公司的上市之路多少被阴影笼罩。​ 业绩波动遭问询 捷瑞数字成立于2000年，公司是一家以数字孪生驱动的工
阅读更多...
大语言模型（LLMs）能够进行推理和规划吗？

大语言模型（LLMs）能够进行推理和规划吗？

大语言模型（LLMs），基本上是经过强化训练的 n-gram 模型，它们在网络规模的语言语料库（实际上，可以说是我们文明的知识库）上进行了训练，展现出了一种超乎预期的语言行为，引发了我们的广泛关注。从训练和操作的角度来看，LLMs 可以被认为是一种巨大的、非真实的记忆库，相当于为我们所有人提供了一个外部的系统 1（见图 1）。然而，它们表面上的多功能性让许多研究者好奇，这些模型是否也能在通常需要系
阅读更多...
百度OCR识别结构结构化处理视频

百度OCR识别结构结构化处理视频

https://edu.csdn.net/course/detail/10506
阅读更多...
如何在Java中处理JSON数据？

如何在Java中处理JSON数据？

如何在Java中处理JSON数据？ 大家好，我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编，也是冬天不穿秋裤，天冷也要风度的程序猿！今天我们将探讨在Java中如何处理JSON数据。JSON（JavaScript Object Notation）作为一种轻量级的数据交换格式，在现代应用程序中被广泛使用。Java通过多种库和API提供了处理JSON的能力，我们将深入了解其用法和最佳
阅读更多...
【杂记-浅谈DHCP动态主机配置协议】

【杂记-浅谈DHCP动态主机配置协议】

DHCP动态主机配置协议 一、DHCP概述1、定义2、作用3、报文类型 二、DHCP的工作原理三、DHCP服务器的配置和管理 一、DHCP概述 1、定义 DHCP，Dynamic Host Configuration Protocol，动态主机配置协议，是一种网络协议，主要用于在IP网络中自动分配和管理IP地址以及其他网络配置参数。 2、作用 DHCP允许计算机和其他设备通
阅读更多...
AI学习指南机器学习篇-朴素贝叶斯处理连续特征和离散特征

AI学习指南机器学习篇-朴素贝叶斯处理连续特征和离散特征

AI学习指南机器学习篇-朴素贝叶斯处理连续特征和离散特征 在机器学习领域，朴素贝叶斯是一种常用的分类算法，它的简单性和高效性使得它在实际应用中得到了广泛的应用。然而，在使用朴素贝叶斯算法进行分类时，我们通常会面临一个重要的问题，就是如何处理连续特征和离散特征。因为朴素贝叶斯算法基于特征的条件独立性假设，所以对于不同类型的特征，我们需要采取不同的处理方式。 在本篇博客中，我们将探讨如何有效地处理
阅读更多...
AI炒股：自动画出A股股票的K线图并添加技术指标

AI炒股：自动画出A股股票的K线图并添加技术指标

在deepseek中输入提示词： 你是一个Python编程专家，要完成一个编写Python脚本的任务，具体步骤如下： 用AKShare库获取股票贵州茅台（股票代码：600519）在2024年3月7日到2024年6月5日期间的历史行情数据-前复权。 然后绘制K线图，并在K线图上添加布林线、MACD 注意： 每一步都要输出信息到屏幕上； 日期格式是YYYYMMDD； 设置中文字体，以解决
阅读更多...
JavaWeb系列六: 动态WEB开发核心(Servlet) 上

JavaWeb系列六: 动态WEB开发核心(Servlet) 上

韩老师学生 官网文档为什么会出现Servlet什么是ServletServlet在JavaWeb项目位置Servlet基本使用Servlet开发方式说明快速入门- 手动开发 servlet浏览器请求Servlet UML分析Servlet生命周期GET和POST请求分发处理通过继承HttpServlet开发ServletIDEA配置ServletServlet注意事项和细节 Servlet注
阅读更多...
神经网络第四篇：推理处理之手写数字识别

神经网络第四篇：推理处理之手写数字识别

到目前为止，我们已经介绍完了神经网络的基本结构，现在用一个图像识别示例对前面的知识作整体的总结。本专题知识点如下： MNIST数据集图像数据转图像神经网络的推理处理批处理  MNIST数据集          mnist数据图像 MNIST数据集由0到9的数字图像构成。像素取值在0到255之间。每个图像数据都相应地标有“7”、“2”、“1”等数字标签。MNIST数据集中，
阅读更多...
vue怎么处理跨域

vue怎么处理跨域

Vue.js 本身并不直接解决跨域问题，因为跨域问题主要是浏览器基于同源策略（Same-origin policy）的一种安全限制。然而，在Vue.js项目中，我们可以采取一些策略来绕过或处理跨域问题。 解决跨域问题的常用方法： 代理服务器：在开发环境中，我们可以配置一个代理服务器来转发API请求，从而绕过浏览器的同源策略。Vue CLI 提供了内置的代理功能，可以在 vue.config.j
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2