【Leetcode刷题篇】leetcode188 买卖股票的最佳时机IV
发布日期:2021-06-29 15:35:12
浏览次数:2
分类:技术文章
本文共 1840 字,大约阅读时间需要 6 分钟。
给定一个整数数组 prices ,它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 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 。提示:
0 <= k <= 109
0 <= prices.length <= 1000 0 <= prices[i] <= 1000
初始化:
如果我们把买+卖算一次交易
那么这道题的限制是交易数,天数,手上有没有股票(有股票就不能买,没有股票就不能卖) 建立三维的数组:dp [k] [i] [2] 其中k表示的是交易次数,i表示的是第几天,2表示的是有两种状态:手上没有股票/手上有股票 dp [k] [i] [0] 数组中的数字表示的是到了第i天,交易了k次,手上没有股票获得的最大利益 dp [k] [i] [1] 数组中的数字表示的是到了第i天,交易了k次,手上持有股票获得的最大利益在我们写转移方程之前我们还要先考虑之前提出来的问题–交易数怎么算,买+卖是一次交易,我的t表示的是交易次数,那我到底是买入的时候t要加一了,还是卖出的时候t才加一?
答:都可以,不同的定义就会有不同的实现
来看一下两者有什么不同
买入就算一次交易: i天t次交易现在手上不持有 = max(i-1天t次交易手上不持有,i-1天t次交易手上持有 + i天卖出价格prices) dp[t] [i] [0] = max(dp[t] [i - 1] [0], dp[t] [i - 1] + prices[i]);i天t次交易现在手上持有 = max(i-1天t次交易手上持有,i-1天t-1次交易手上不持有 - i天买入价格)
dp[t] [i] [1] = max(dp[t] [i - 1] [1], dp[t - 1] [i - 1] [0] - prices[i])初始化
dp[t] [0] [0] 0天t次交易,手上不持有:可能的 0
dp[t] [0] [1] 0天t次交易,手上持有:不可能(0天没有股票,所以无法买入持有;持有说明至少进行了一次买入,买入就交易,因此这里不可能【不可能意思就是不能从这里转移】 dp[0] [i] [0] i天0次交易,手上不持有:0 dp[0] [i] [1] i天0次交易,手上持有:不可能(不交易手上不可能持有)
class Solution { public int maxProfit(int k, int[] prices) { if(prices==null||prices.length==0||prices.length==1) { return 0; } // 判断k次交易 if(k>(prices.length/2)) { int sum = 0; for(int i=1;i0?temp:0); } return sum; } // 动态数组 int[][][] dp = new int[k+1][prices.length+1][2]; // 初始化 交易 0天t次交易 手上持有 不可能 for(int t=0;t<=k;t++) { dp[t][0][1] = Integer.MIN_VALUE; } // i天0次交易手上持有 不可能 for(int i=0;i
转载地址:https://codingchaozhang.blog.csdn.net/article/details/111309017 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
不错!
[***.144.177.141]2024年05月01日 18时21分46秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Python 管理程序改进——连接MYSQL
2019-04-29
Python 爬虫
2019-04-29
Python 爬虫-百度风云榜的电影top50
2019-04-29
Python 爬虫-豆瓣影星图片下载
2019-04-29
Excel数据基础操作
2019-04-29
网页端数据库操作界面—主题函数文件
2019-04-29
网页端数据库操作界面-Html页面(1)
2019-04-29
网页端数据库操作界面-Html页面(2)
2019-04-29
网页端数据库操作界面-Html页面(3)
2019-04-29
Excel 高级筛选
2019-04-29
Python爬虫 百度热搜热点
2019-04-29
Python 百度热搜 全页面爬取
2019-04-29
爬取小说——爬取书的地址
2019-04-29
爬取小说——爬取章节地址
2019-04-29
爬取小说——爬取标题和正文
2019-04-29
爬取小说——储存为TXT格式
2019-04-29
爬取小说——主体部分
2019-04-29
Python 窗口化操作
2019-04-29
excel的常用函数(二)
2019-04-29
excel的逻辑函数
2019-04-29