[309][中等][动态规划] 最佳买卖股票时机含冷冻期

题目描述

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

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

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

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

示例:

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

解题思路

动态规划是一个比较直接的思路. 题目求解的其实是最后一天的最大利润, 很容易想到将第$i$天的最大利润作为状态, 这样最后的答案就是最后一天的数值.

接下来就是考虑状态转移方程, 这与交易的状态是息息相关的. 一般来说有两种状态, 持有和空仓, 由于本题增加了一个冷冻期, 因此是持有, 冷冻期空仓, 空仓三种状态.

考虑每一天状态的定义, 由于买入和卖出操作, 会使一天的状态发生改变:

• 买入: 由空仓到持有, 冷冻期空仓不能转为持有, 即不能买入

• 卖出: 持有到冷冻期

因此, 每天用一个状态来表示的话, 需要将每一天的状态定义为操作前, 或操作后. 这里使用操作后的状态, 即有买入行为的一天定义为持有状态, 有卖出行为的定义为冷冻期状态. 这样对于三种状态, 可能的来源是:

• 持有

  • 上一天已经持有

  • 当天买入

• 冻结期

  • 当天卖出

• 空仓

  • 上一天空仓

  • 上一天冻结期

综上所述, 结合逻辑, 状态的转移是有一定的逻辑关系的, 因此, 需要每种状态在每天的表现, 我们的转移方程就能从状态的切换和相互之间的关系出发.

因此, 定义三个序列, 分别记录第$i$天, 作为持有, 冷冻期空仓, 空仓三种状态的最大利润, 即 $\text{dp1}$, $\text{dp2}$, $\text{dp3}$, 如$\text{dp2}[i]$就代表第$i$天结束为冷冻期状态下的最大利润.

然后我们定义利润. 一次买卖中间的差价肯定是利润. 另外, 需要注意的是, 根据世界通用的浮赢不算赢, 落袋才算赚的原则, 如果我们买入之后一直没有卖出行为, 就算涨的再多也不算赚钱. 此外, 我们的资金只看落袋的金额, 持有状态下股票的价值, 是不应该计入到账户资金中的, 即买入一支股票相当于暂时损失了这笔钱.

现在我们可以定义初始状态和状态转移方程了. 首先定义初始状态. 首先天数要不小于两天, 否则一买一卖的操作都无法完成, 利润最大肯定是0. 初始状态第一天, 持有状态相当于第一天买入, 冻结期状态不存在, 利润设置为0, 空仓状态相当于不操作, 利润也为0. 因此初始状态初始化为:

$\text{dp1}[0]=-\text{prices}[0],\qquad \text{dp2}[0]=0,\qquad \text{dp3}[0]=0$

状态转移方程.

• 对于持有状态, 如果上一天已经持有, 那利润等于上一天持有状态的利润(之前某一天扣除过买入价后的利润); 如果是当天买入, 利润是上一天空仓状态的利润减去当天的价格. 两者取其大

  $\text{dp1}[i] = \max(\text{dp1}[i-1],\text{dp2}[i-1]-\text{prices}[i])$

• 对于冻结期状态, 只有当天卖出才会转移, 利润等于上一天持有利润加上当日卖出的价格

  $\text{dp2}[i] = \text{dp1}[i-1] + \text{prices}[i]$

• 对于空仓状态, 如果上一天也空仓, 利润直接等于上一天空仓状态的利润; 还有一种是上一天是冻结期, 利润等于冻结期状态上一天的利润

  $\text{dp3}[i] = \max(\text{dp2}[i - 1], \text{dp3}[i - i])$

最终的最大利润会在最后一天冷冻期和空仓的状态下产生, 持有状态下的部分利润被在仓的股票占用了, 肯定不是最大利润.

综上所述, 代码如下:

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

        dp1 = [-prices[0]]  # 持有状态
        dp2 = [0]  # 冻结期
        dp3 = [0]  # 空仓

        for i in range(1, n):
            dp1.append(max(dp1[i - 1], dp3[i - 1] - prices[i]))
            dp2.append(dp1[i - 1] + prices[i])
            dp3.append(max(dp3[i - 1], dp2[i - 1]))
        return max(dp2[-1], dp3[-1])