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

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

文章目录

• • • 题目
    • 思路
    • 代码
    • 运行结果
    • 总结

题目

'''
Description: 309.买卖股票时机含冷冻期
Autor: 365JHWZGo
Date: 2021-12-11 16:11:55
LastEditors: 365JHWZGo
LastEditTime: 2021-12-12 14:24:31
'''

思路

直观解题思路:
            这道题的特点是含有一个冷冻期，那么重点就在于如何确定冷冻期的位置
            我们知道在冷冻期的时候，利润是不会变的，所以它的利润为前面股票卖出的利润
思路:
        1.确定dp数组以及下标含义
            每一天的股票有四种状态
            0 不买入
            1 买入
            2 卖出
            3 冷冻
            dp[i][j]代表第i天在第j种状态下的最大收益为dp[i][j]
        2.确定递推公式
            # 买入【必须是经历过冷冻期才能买入】｜不买入
            dp[i][1] = max(dp[i-1][3]-prices[i], dp[i-1][1])
            # 卖出｜不卖出
            dp[i][2] = max(dp[i-1][1]+prices[i],dp[i-1][2])
            # 冷冻期
            # 当第i个为冷冻期的时候，它的前一个状态必须是卖出dp[i-1][2]
            dp[i][3] = dp[i-1][2]
        3.初始化dp数组
            dp[0][1] = -prices[0] 
        4.确定遍历顺序
            从前往后依次遍历
        5.举例推导
        	prices = [1,2,3,0,2]
           dp [[0, -1, 0, 0], [0, -1, 1, 0], [0, -1, 2, 1], [0, 1, 2, 2], [0, 1, 3, 2]]
3

不买入买入卖出冷冻期10-10020Max(0-2,-1)=-1Max(-1+2,0)=1030Max(0-3,-1)=-1Max(-1+3,1)=2100Max(1-0,-1)=1Max(-1+0,2)=2220Max(2-2,1)=1Max(1+2,2)=32 代码

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if len(prices) == 1:
            return 0
        #  0 不买入 1 买入  2 卖出  3 冷冻
        stockState = 4
        dp = [[0 for _ in range(stockState)]for _ in range(len(prices))]
        dp[0][1] = -prices[0]  

        for i in range(1, len(prices)):
            
            # 买入【必须是经历过冷冻期才能买入】｜不买入
            dp[i][1] = max(dp[i-1][3]-prices[i], dp[i-1][1])
            # 卖出｜不卖出
            dp[i][2] = max(dp[i-1][1]+prices[i],dp[i-1][2])
            # 冷冻
            # 当第i个为冷冻的时候，它的前一个状态必须是卖出dp[i-1][2]
            dp[i][3] = dp[i-1][2]
                    
        # print(dp)
        return max(dp[-1])

运行结果

总结

这道题总体上来说也是很难的，因为想了很久，但好在有前面的题做铺垫，就可以构造思路，创造出当前股票有的n种状态，然后分别判断处于各种状态的股票的最大利润是多少，最后得出结论。