共计 1646 个字符，预计需要花费 5 分钟才能阅读完成。
309. 最佳交易股票机会含冷冻期
题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown
题目
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格。
设计一个算法计算出最大利润。在满足以下约束条件下，你能够尽可能地实现更多的交易（屡次交易一支股票）:
- 你不能同时参加多笔交易（你必须在再次购买前发售掉之前的股票）。
- 卖出股票后，你无奈在第二天买入股票 (即冷冻期为 1 天)。
示例:
输出: [1,2,3,0,2]
输入: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]解题思路
思路：动静布局
先审题，题目中阐明，不能同时参加多笔交易，购买前需先抛售后面购买的股票。同时还会有一个 冷冻期，题目给出的解释是当某一天抛售股票时，第二天无奈再次购买也就是抛售后的第二天劳动一天。
因为交易有这个冷冻期的存在，咱们先将是否持有股票辨别开，再将这个概念增加进来探讨。先定义两个 dp 数组，别离代表持有股票和未持有股票的累计最大收益。
状态定义
先进行状态定义，定义两个数组别离为 own 和 not_own。其中 own[i] 示意第 i 地利，持有股票的最大收益；而 not_own[i] 示意第 i 地利，未持有股票的最大收益。
状态转移
当初探讨 冷冻期 这个概念，下面两个数组，在进行状态转移的时候会有不同的状况，具体如下：
对于 own[i] 而言，示意第 i 天持有股票的最大收益，可能状况拆分如下：
- 第
i-1天持有，第i天持续持有； - 第
i-1天为冷冻期，那么第i天买入（也就是前天卖了，当天买入价格为prices[i]）； - 那么此时的状态转移方程为：
own[i] = max(own[i-1], not_own[i-2] - prices[i])
对于 not_own[i] 而言，也能够拆分为以下状况：
- 第
i-1天抛售，第i天属于冷冻期； - 第
i-1天持有股票，第i天抛售股票； - 那么此时的状态转移方程为：
not_own[i] = max(not_own[i-1], own[i-1]+prices[i])
在这里，两个数组之间产生状态转移。先说下 own[i] 的状态转移方程，对于第一种状况好了解，第二种状况，能够这样了解，因为相近一次交易的收益是这样计算的：收益 = 卖出 – 买入。那么当天买入须要花的钱间接先扣除（也就是先减去买入价格），那么后续抛售的时候，这里就不再计算这一部分，间接加上卖出的价格。这种状况也就跟 not_own[i] 呈现的第二种状况吻合，间接用后面第 i-1 天的收益加上以后股票的价格（因为后面曾经先扣除过）。
初始化
own[0]：示意第 0 天买入，后面剖析了，这里间接减去买入价格，所以 own[0] = -prices[0]；
own[1]：示意可能第 0 天买入，第 1 天持续持有；或者第 1 天当天买入，所以 own[1] = max(-prices[0], -prices[1])。
not_own[0]：示意第 0 天未持有股票，所以无收益，not_own[0] = 0
具体代码实现如下。
代码实现
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices or len(prices) == 1:
return 0
length = len(prices)
own = [0] * length
not_own = [0] * length
# 初始化
own[0] = -prices[0]
own[1] = max(-prices[0], -prices[1])
not_own[0] = 0
for i in range(1, length):
not_own[i] = max(not_own[i-1], own[i-1] + prices[i])
if i == 1:
continue
own[i] = max(own[i-1], not_own[i-2] - prices[i])
return max(own[-1], not_own[-1])实现后果
欢送关注
公众号【书所集录】
