买卖股票的最佳时机包括冻结期,力扣,刷题,Python,笔记,含,冷冻

发表时间:2020-12-25

题目

给定一个整数数组,其中第 i 个元素代表了第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):

你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。
在这里插入图片描述
来源:力扣(LeetCode)

Python解法

动态规划解法

具体的解题思路如下:

  • 首先计算 prices 的长度 n,如果 n 小于2,那么直接返回0;
  • 建立一个长度为 n、初始元素为 [0, 0] 的数组 dp,则可以用 dp[i][0] 来选取数组的数组的元素,dp[][] 这两个框中前面代表天数,后面代表是否持有股票,对应的值就是对应的利润最大值;
  • dp[i][0] 代表第 i-1 天不持股或者第 i-1 天持股然后第 i 天卖出;
  • dp[i][1] 有所不同,按照正常的理解应该是第 i-1 天持股或者第 i-1 天不持股然后第 i 天持股,但是这里有一个冷冻期,是需要隔一天的,因此如果你在第 i-1 天不持股那么在第 i-2 天一定也不能持股,否则第 i-2 天持股在第 i-1 天不持股说明在第 i-1 天卖出,那么第 i 天是冷冻期,是不允许持股的。因此对于 dp[i][1] 来说,第 i-1 天如果不持股,那么第 i-2 天也不应该持股,这样将 第 i-1 天作为冷冻期,第 i 天才能持股;
  • 最后返回dp[-1][0]因为不持股利润是要大于等于持股的。

代码如下:

def maxProfit(self, prices: List[int]) -> int:
    n = len(prices)
    if n < 2: return 0
    dp = [[0,0] for i in range(n)]   #dp的初始化

    dp[0][0] = 0     #第0天不持股自然就为0了
    dp[0][1] = -prices[0]   #第0天持股,那么价格就是-prices[0]了
    #第1天不持股,要么第0天就不持股,要么就是第0天持股,然后第1天卖出
    dp[1][0] = max(dp[0][0],dp[0][1]+prices[1]) 
    #第一天持股,要么就是第0天就持股了,要么就是第0天不持股第1天持股
    dp[1][1] = max(dp[0][1],dp[0][0]-prices[1])
    
    for i in range(2,n):
        dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i])
        dp[i][1] = max(dp[i-1][1],dp[i-2][0]-prices[i])
    return dp[-1][0]

文章来源互联网,如有侵权,请联系管理员删除。邮箱:417803890@qq.com / QQ:417803890

微配音

Python Free

邮箱:417803890@qq.com
QQ:417803890

皖ICP备19001818号
© 2019 copyright www.pythonf.cn - All rights reserved

微信扫一扫关注公众号:

联系方式

Python Free