题目链接

买卖股票的最佳时机含冰冻期

题目描述

image.png

实现代码

分析：假设f[i]表示第i个位置的最大利润，每个位置都是对应了两个状态：持有和未持有，而未持有又对应着两个状态：之前就未持有和今天刚卖的，因此可以将其划分为下面几个状态对应关系：

  1. f[i][0]：在i位置持有股票
  2. f[i][1]：在i位置未持有股票，且不是今天卖出的，不算冷冻期
  3. f[i][2]：在i位置未持有股票，且是今天卖出的，算冷冻期

这样划分的话，每个状态的最大利润就跟i-1位置的最大利润能扯上关系了：

  1. f[i][0] = max(f[i-1][0], f[i-1][1] - price[i])
  2. f[i][1] = max(f[i-1][1], f[i-1][2])
  3. f[i][2] = f[i][0] + price[i]

实现代码如下：

  1. class Solution:
  2.     def maxProfit(self, prices: List[int]) -> int:
  4.         n = len(prices)
  5.         if n == 1:
  6.             return 0
  8.         '''
  9.             每个i位置都对应三种状态：
  10.             1. 当前位置持股 对应f[i][0]
  11.             2. 当前位置未持股且不是冷冻期(即不是今天卖的) 对应f[i][1]
  12.             3. 当前位置为持股且是冷冻期(即是今天卖的) 对应f[i][2]
  13.         '''
  15.         # f = [[-prices[0], 0, 0]] + [[0] * 3 for _ in range(n - 1)]
  17.         f_zero = -prices[0]
  18.         f_one = 0
  19.         f_two = 0
  21.         first = True
  23.         for idx, price in enumerate(prices):
  25.             if first:
  26.                 first = False
  27.                 continue
  29.             temp_zero = f_zero
  30.             temp_one = f_one
  31.             temp_two = f_two
  33.             f_zero = max(temp_zero, temp_one - price)
  34.             f_one = max(temp_one, temp_two)
  35.             f_two = temp_zero + price
  37.             # f[idx][0] = max(f[idx - 1][0], f[idx - 1][1] - price)
  38.             # f[idx][1] = max(f[idx - 1][1], f[idx - 1][2])
  39.             # f[idx][2] = f[idx - 1][0] + price
  41.         return max(f_one, f_two)