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

• 2020 年 7 月 14 日
• 筆記
• 力扣中国-每日一题

from typing import List
# 用动态规划的写法来写题。
# 每一天都有五种情况发生，
#1，今天买入，2，今天卖出，3今天是冷冻期，4，今天不买入也不卖出（没有持有股票）5，今天不买入也不卖出（持有股票）
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 当天数小于二时，无法进行买卖交易，因此直接返回零
        if len(prices) <= 1:return 0
        # 定义列表表示状态方程
        dp = [[0,0,0,0,0] for _ in range(len(prices)) ]
        # 定义初始值的状态
        # 今天买入的利润为负值
        dp[0][0] = -prices[0]
        # 第一天不可能卖出
        dp[0][1] = float("-inf")
        # 第一天不可能处于冷冻期
        dp[0][2] = float("-inf")
        # 不进行交易利润为零
        dp[0][3] = 0
        # 第一天不可能持有股票，同时不交易
        dp[0][4] = float("-inf")
        # 进行遍历
        for index in range(1,len(prices)):
            # 今天买入，昨天可能是冷冻期，或者没有交易
            dp[index][0] = max(dp[index - 1][3],dp[index - 1][2]) - prices[index]
            # 今天卖出，可能是昨天买入的，也可能是昨天已经持有但没有交易
            dp[index][1] = max(dp[index - 1][0],dp[index - 1][4]) + prices[index]
            # 今天为冷冻期代表昨天卖出
            dp[index][2] = dp[index - 1][1]
            #今天不交易，昨天可能是冷冻期，或者昨天就不交易
            dp[index][3] = max(dp[index -1][3],dp[index - 1][2])
            # 今天不交易（但持有股票），可能是昨天就没有交易同时持有股票，也可能是昨天刚买的股票。
            dp[index][4] = max(dp[index - 1][4],dp[index - 1][0])
        return max(dp[-1])

A = Solution()
print(A.maxProfit([1,2,3,0,2]))