买卖股票的最佳时期含冷冻期

题目表述

给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。​

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

卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1

输入: prices = [1,2,3,0,2]

输出: 3

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

示例 2

输入: prices = [1]

输出: 0

提示

1 <= prices.length <= 5000

0 <= prices[i] <= 1000

解法一：动态规划

将买入记为负收益，卖出记为正收益，目标是最大化收益。

设dp0[i] 表示第 i 天不持有股票且未处于冷冻期的收益，设dp1[i] 表示第 i 天不持有股票且处于冷冻期的收益，设dp2[i] 表示第 i 天持有股票的收益。则有状态转移方程：

对于dp0[i]：

1. 前一天未持有股票未处于冷冻期

2. 前一天未持有股票处于冷冻期

$$dp0[i]=max(dp0[i-1],dp1[i-1])$$

且dp0[0]=0

对于dp1[i]，前一天必定持有股票：

$$dp1[i]=dp2[i-1]+prices[i]$$

且dp1[0]=0

对于dp2[i]:

1. 持有的股票是之前买入的

2. 持有的股票是今天买入的，相应的前一天未持有股票且不处于冷冻期

$$dp2[i]=max(dp2[i-1],dp0[i-1]-prices[i])$$

且dp2[0]=-prices[0]

代码实现

from typing import List


class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp0 = dp1 = 0
        dp2 = -prices[0]
        for i in range(1, len(prices)):
            dp0, dp1, dp2 = max(dp0, dp1), dp2+prices[i], max(dp2, dp0-prices[i])
        return max(dp0, dp1)

package leetcode

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func maxProfit(prices []int) int {
	dp0, dp1, dp2 := 0, 0, -prices[0]
	for _, v := range prices[1:] {
		dp0, dp1, dp2 = max(dp0, dp1), dp2+v, max(dp2, dp0-v)
	}
	return max(dp0, dp1)
}