LeetCode 188. 买卖股票的最佳时机 IV(Best Time to Buy and Sell Stock IV)
发布日期:2021-06-29 17:11:19
浏览次数:2
分类:技术文章
本文共 2043 字,大约阅读时间需要 6 分钟。
LeetCode.jpg
给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。注意: 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。示例 1:输入: [2,4,1], k = 2输出: 2解释: 在第 1 天 (股票价格 = 2) 的时候买入,在第 2 天 (股票价格 = 4) 的时候卖出,这笔交易所能获得利润 = 4-2 = 2 。示例 2:输入: [3,2,6,5,0,3], k = 2输出: 7解释: 在第 2 天 (股票价格 = 2) 的时候买入,在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。 随后,在第 5 天 (股票价格 = 0) 的时候买入,在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
Python3 实现
动态规划
买卖股票的最佳时机 系列问题 通用型 解法 ,LeetCode 121 123 均可参考此方法
# @author:leacoder # @des: 动态规划 买卖股票的最佳时机 IV(通用型) class Solution: def maxProfit(self, k: int, prices: List[int]) -> int: n = len(prices) if n<=1: return 0 if k>int(n/2): # 会超时 #k = int(n/2) return self.greedy(prices) # 使用贪心 maxprof = 0 profit = [[[0 for _ in range(2)] for _ in range(k+1)] for _ in range(0,len(prices))] # DP[ii][kk][0] 第ii天完成kk次操作无股票 DP[ii][kk][1]第ii天完成kk次操作有股票 prices[ii] 第ii天股票价格 for i in range(0,k+1): profit[0][i][0] = 0 # 第 1 天 操作i 次 没有股票,所以初始值为 0 profit[0][i][1] = - prices[0] # 第 1 天 操作i 次 有股票, 所以初始值为 - prices[ii] for ii in range(1,len(prices)): # 天数 for kk in range(0, k + 1): # 交易次数 if kk == 0: # profit[ii][kk][0] = profit[ii - 1][kk][0] # 0 次交易 今天利润 == 前一天利润 else: # 今天完成kk次操作无股票 max(前一天无股票今天不交易,前一天有股票今天卖出) 买卖一次算一笔交易 故 profit[ii - 1][kk - 1][1] + prices[ii] profit[ii][kk][0] = max(profit[ii - 1][kk][0], profit[ii - 1][kk - 1][1] + prices[ii]) # 今天完成kk次操作有股票 max(前一天有股票今天不交易,前一天无股票今天买入) profit[ii][kk][1] = max(profit[ii - 1][kk][1], profit[ii - 1][kk][0] - prices[ii]) maxprof = max(maxprof, profit[ii][kk][0]) return maxprof def greedy(self,prices: List[int]) -> int: max = 0 for i in range(1,len(prices)): if prices[i]>prices[i-1]: max += prices[i] - prices[i-1] return max
GitHub链接:
知乎个人首页:简书个人首页:个人Blog:欢迎大家来一起交流学习
转载地址:https://blog.csdn.net/leacock1991/article/details/101467175 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
第一次来,支持一个
[***.219.124.196]2024年04月12日 00时35分06秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
常用电子接口大全,遇到不认识的,就翻出来对照辨认!
2019-04-29
芯片IC附近为啥要放0.1uF的电容?
2019-04-29
电赛 | 19年全国一等奖,北航学子回忆录。
2019-04-29
电赛 | 19年全国一等奖,北航学子回忆录(上)
2019-04-29
电赛 | 19年全国一等奖,北航学子回忆录(下)
2019-04-29
突破!台积电1nm芯片,有了新进展。
2019-04-29
一文读懂全系列树莓派!
2019-04-29
自制一个害羞的口罩,见人就闭嘴,戴着可以喝奶茶
2019-04-29
聊聊我是如何编程入门的
2019-04-29
J-Link该如何升级固件?
2019-04-29
485通信自动收发电路,历史上最详细的解释
2019-04-29
「第三篇」全国电子设计竞赛,这些你必须知道的比赛细节,文末附上近十年电赛题目下载...
2019-04-29
5G小科普(漫画版,So easy!)
2019-04-29
「第四篇」电赛控制题可以准备一些什么?
2019-04-29
树莓派翻车了
2019-04-29
这位电子工程师,你不能错过。
2019-04-29
干货分享 JVM 之第 3 篇 —— Java 内存结构相关
2019-04-29
UR5e机械臂运行一直阻塞在waitForServer
2019-04-29
ROS把pkg1下的某个头文件和源文件生成动态链接库供pkg2调用
2019-04-29