Java通过动态规划设计股票买卖最佳时机
买卖股票的最佳时机
给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。
示例:
链接:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock
动态规划
因为对每一天只有两个状态,买入股票和卖出股票,因此定义 dp[][2]
1. dp[i][2] 数组表示的含义 :
dp[i][0] 表示第 i 天买入股票能获得的最大利润,dp[i][1] 表示第一天卖出股票能获得的最大利润
2. 状态转移方程:
dp[i][0] = max(dp[i-1][0], -prices[i])
解释: 第 i 天对买入股票状态,只有两种操作,买入股票或者不买股票。因此,第 i 天能获得的最大利润为 第 i 天不买股票(dp[i-1][0]
) 和 第 i 天买入股票(-prices[i]
) 的利润的最大值。
dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])
解释: 第 i 天对卖出股票,只有两种操作,卖出股票或者不卖出股票。因此,第 i 天能获得的最大利润为 第 i 天卖出股票 (dp[i-1][0] + prices[i]
)和 第 i 天不卖出股票 的利润的最大值 (dp[i-1][1]
)
3. 初始化
第 0 天买入,得到的利润为 -price[0]
第 0 天卖出,得到的利润为 0
dp[0][0] = -price[0] dp[0][1] = 0
代码:
// 买卖股票的最佳时机 public int maxProfit(int[] prices) { // dp 表示当天能获得的最大利润 int[][] dp = new int[prices.length][2]; // 对每一天来说,就两个状态,一个是买入,一个是卖出 dp[0][0] = -prices[0]; // 第一天买入 dp[0][1] = 0; // 第一天卖出 for(int i=1; i<prices.length; i++){ dp[i][0] = Math.max(dp[i-1][0], -prices[i]); dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i]); } return dp[prices.length-1][1]; }
变式一: 可以重复买入,卖出
// 买卖股票的最佳时机2 —— 可以多次买入和卖出,但是注意每次只能持有一张股票,就是必须是 买 - 卖 - 买 - 卖 - 买 - 卖 ....这种顺序 public int maxProfit2(int[] prices) { // 本题与上题的区别就在于状态转移方程不同 -- 本题可以用之前得到的利润 (即 dp[i-1][1],上一轮卖出后剩下的钱) 再去买入,而上一题必须 0-price[i] 买入 // dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]-prices[i]); ---- 买入股票能得到的最大利润状态转移方程有变化 int[][] dp = new int[prices.length][2]; dp[0][0] = -prices[0]; dp[0][1] = 0; for(int i=1; i<prices.length; i++){ dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i]); // 当天可能执行股票买入 dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i]); // 当他可能执行股票卖出 } return dp[prices.length-1][1]; }
变式二:可以执行买入卖出操作两次
// 买卖股票的最佳时机3 —— 本题与上一题的区别在于,本题只能执行两次买入、卖出操作 public int maxProfit3(int[] prices) { // 每次可执行的操作状态为 ,第一次买入、第一次卖出、第二次买入、第二次卖出,因此 dp 定义为 int[][] dp = new int[prices.length][4]; dp[0][0] = -prices[0]; dp[0][1] = 0; dp[0][2] = -prices[0]; dp[0][3] = 0; for(int i=1; i<prices.length; i++){ dp[i][0] = Math.max(dp[i-1][0], -prices[i]); dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i]); dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1] - prices[i]); dp[i][3] = Math.max(dp[i-1][3], dp[i-1][2] + prices[i]); } return dp[prices.length-1][3]; }
变式三:可以执行买卖操作 K 次
// 买卖股票的最佳时期 —— 最多进行 K 次交易 public int maxProfit(int k, int[] prices) { // 就是两次交易的升级版 int[][] dp = new int[prices.length][2*k+1]; // 奇数表示买入,偶数表示卖出 // 初始化 for(int j=1; j<2*k; j+=2){ dp[0][j] = -prices[0]; } for(int i=1; i<prices.length; i++){ for(int j=0; j<2*k-1; 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]); } } return dp[prices.length-1][2*k]; }
变式四:含冷冻期
// 买卖股票含冷冻期 public int maxProfit(int[] prices) { // 一共四种状态 买入 卖出(早就卖出保存卖出态,当天卖出) 冷冻 int dp[][] = new int[prices.length][4]; // 初始化 dp[0][0] = -prices[0]; for(int i=1; i<prices.length; i++){ // 买入状态 —— 前一天就是买入状态 + 前一天是卖出状态今天买入了 + 前一天是冷冻状态今天买入了 dp[i][0] = Math.max(dp[i-1][0], Math.max(dp[i-1][3]-prices[i], dp[i-1][2]-prices[i]) ); // 卖出态1 —— 前一天就是卖出态1 + 前一天是冷冻态 dp[i][1] = Math.max(dp[i-1][1], dp[i-1][3]); // 卖出态2 —— 当天卖出了 dp[i][2] = dp[i-1][0] + prices[i]; // 冷冻态 —— 前一天是卖出态2 dp[i][3] = dp[i-1][2]; } return Math.max(dp[prices.length-1][1], Math.max(dp[prices.length-1][2], dp[prices.length-1][3])); }
变式五:含手续费
// 买卖股票的最佳时机,含手续费 public int maxProfit2(int[] prices, int fee) { int[][] dp = new int[prices.length][2]; // 初始化 dp[0][0] = -prices[0] - fee; for(int i=1; i<prices.length; i++){ dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i] - fee); dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i]); } return dp[prices.length-1][1]; }
到此这篇关于Java通过动态规划设计股票买卖最佳时机的文章就介绍到这了,更多相关Java股票买卖内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!
原文出处:https://blog.csdn.net/liuwanqing233333/article/details/12740
相关文章
- 这篇文章主要介绍了如何利用java语言实现经典《复杂迷宫》游戏,文中采用了swing技术进行了界面化处理,感兴趣的小伙伴可以动手试一试...2022-02-01
java 运行报错has been compiled by a more recent version of the Java Runtime
java 运行报错has been compiled by a more recent version of the Java Runtime (class file version 54.0)...2021-04-01- 这篇文章主要介绍了在java中获取List集合中最大的日期时间操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 这篇文章主要介绍了教你怎么用Java获取国家法定节假日,文中有非常详细的代码示例,对正在学习java的小伙伴们有非常好的帮助,需要的朋友可以参考下...2021-04-23
- 这篇文章主要介绍了Java如何发起http请求的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-03-31
- 说起C#和Java这两门语言(语法,数据类型 等),个人以为,大概有90%以上的相似,甚至可以认为几乎一样。但是在工作中,我也发现了一些细微的差别...2020-06-25
- 这篇文章主要介绍了解决Java处理HTTP请求超时的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-29
- 这篇文章主要介绍了java 判断两个时间段是否重叠的案例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
java 画pdf用itext调整表格宽度、自定义各个列宽的方法
这篇文章主要介绍了java 画pdf用itext调整表格宽度、自定义各个列宽的方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-01-31- 这篇文章主要介绍了超简洁java实现双色球若干注随机号码生成(实例代码),本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-04-02
- 这篇文章主要介绍了Java生成随机姓名、性别和年龄的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-10-01
- 这篇文章主要介绍了java正则表达式判断前端参数修改表中另一个字段的值,需要的朋友可以参考下...2021-05-07
Java使用ScriptEngine动态执行代码(附Java几种动态执行代码比较)
这篇文章主要介绍了Java使用ScriptEngine动态执行代码,并且分享Java几种动态执行代码比较,需要的朋友可以参考下...2021-04-15- 这篇文章主要介绍了Java开发实现人机猜拳游戏,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-08-03
Java 8 Stream 的终极技巧——Collectors 功能与操作方法详解
这篇文章主要介绍了Java 8 Stream Collectors 功能与操作方法,结合实例形式详细分析了Java 8 Stream Collectors 功能、操作方法及相关注意事项,需要的朋友可以参考下...2020-05-20- 这篇文章主要介绍了Java List集合返回值去掉中括号('[ ]')的操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-29
Java中lombok的@Builder注解的解析与简单使用详解
这篇文章主要介绍了Java中lombok的@Builder注解的解析与简单使用,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-01-06- 下面小编就为大家带来一篇java中String类型变量的赋值问题介绍。小编觉得挺不错的。现在分享给大家,给大家一个参考。...2016-03-28
- 这篇文章主要介绍了Java线程池中的各个参数如何合理设置操作,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教...2021-06-19
- 在Java中,我们可以利用多线程来最大化地压榨CPU多核计算的能力,下面这篇文章主要给大家介绍了关于java中多线程与线程池基本使用的相关资料,需要的朋友可以参考下...2021-09-13