欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

荐 LeetCode 309. 最佳买卖股票时机含冷冻期 | Python

程序员文章站 2022-06-09 18:07:44
使用动态规划,解决《309. 最佳买卖股票时机含冷冻期》问题...

309. 最佳买卖股票时机含冷冻期


题目来源:力扣(LeetCode)https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown

题目


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

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

  • 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
  • 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。

示例:

输入: [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

解题思路


思路:动态规划

先审题,题目中说明,不能同时参与多笔交易,购买前需先抛售前面购买的股票。同时还会有一个冷冻期,题目给出的解释是当某一天抛售股票时,第二天无法再次购买也就是抛售后的第二天休息一天。

因为买卖有这个冷冻期的存在,我们先将是否持有股票区分开,再将这个概念添加进来讨论。先定义两个 dp 数组,分别代表持有股票和未持有股票的累计最大收益。

状态定义

先进行状态定义,定义两个数组分别为 ownnot_own。其中 own[i] 表示第 i 天时,持有股票的最大收益;而 not_own[i] 表示第 i 天时,未持有股票的最大收益。

状态转移

现在讨论 冷冻期 这个概念,上面两个数组,在进行状态转移的时候会有不同的情况,具体如下:

对于 own[i] 而言,表示第 i 天持有股票的最大收益,可能情况拆分如下:

  • i-1 天持有,第 i 天继续持有;
  • i-1 天为冷冻期,那么第 i 天买入(也就是前天卖了,当天买入价格为 prices[i]);
  • 那么此时的状态转移方程为:own[i] = max(own[i-1], not_own[i-2] - prices[i])

对于 not_own[i] 而言,也可以拆分为以下情况:

  • i-1 天抛售,第 i 天属于冷冻期;
  • i-1 天持有股票,第 i 天抛售股票;
  • 那么此时的状态转移方程为:not_own[i] = max(not_own[i-1], own[i-1]+prices[i])

在这里,两个数组之间发生状态转移。先说下 own[i] 的状态转移方程,对于第一种情况好理解,第二种情况,可以这样理解,因为相近一次买卖的收益是这样计算的:收益 = 卖出 - 买入。那么当天买入需要花的钱直接先扣除(也就是先减去买入价格),那么后续抛售的时候,这里就不再计算这一部分,直接加上卖出的价格。这种情况也就跟 not_own[i] 出现的第二种情况吻合,直接用前面第 i-1 天的收益加上当前股票的价格(因为前面已经先扣除过)。

初始化

own[0]:表示第 0 天买入,前面分析了,这里直接减去买入价格,所以 own[0] = -prices[0]

own[1]:表示可能第 0 天买入,第 1 天继续持有;或者第 1 天当天买入,所以 own[1] = max(-prices[0], -prices[1])

not_own[0]:表示第 0 天未持有股票,所以无收益,not_own[0] = 0

具体代码实现如下。

代码实现


class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices or len(prices) == 1:
            return 0

        length = len(prices)

        own = [0] * length
        not_own = [0] * length

        # 初始化
        own[0] = -prices[0]
        own[1] = max(-prices[0], -prices[1])

        not_own[0] = 0

        for i in range(1, length):
            not_own[i] = max(not_own[i-1], own[i-1] + prices[i])
            if i == 1:
                continue
            own[i] = max(own[i-1], not_own[i-2] - prices[i])
        
        return max(own[-1], not_own[-1])

实现结果


荐
                                                        LeetCode 309. 最佳买卖股票时机含冷冻期 | Python

欢迎关注


公众号 【书所集录

本文地址:https://blog.csdn.net/weixin_45642918/article/details/107256359