题目
难度：★★★★☆
类型：数组
方法：动态规划，分类讨论
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
示例:
输入: [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
解答
建立dp矩阵，矩阵的维度为n行3列，其中：
dp[i][0]表示第i天持有股票的情况下的当前收益。
dp[i][1]表示第i天处于未持有股票，但是处于冷冻期状态下的当前收益；
dp[i][2]表示第i天处于未持有股票，也不在冷冻期状态下的当前收益。
逐行（天）计算这三个状态的数值，当天买入记为负收益，当天卖出记为正收益。
初始情况：
dp[0][0] = -prices[0]，第一天买入，当前累计收益为负值，数值上是第一天的价格。
dp[0][1] = dp[0][2]=0，第一天未持有股票，当前累计收益为零。
递推公式：
第i天持有（或买入）股票，这一天的累计收益值有两种情况：
第一，这一天之前已经持有股票，则对应的收益为dp[i-1][0]；
第二，这一天之前（前一天）处于非冷冻期的未持有股票状态，但是这一天买入，对应的累计收益为dp[i-1][2] - prices[i]
dp[i][0] = max(dp[i-1][0], dp[i-1][2] - prices[i])第i天处于冷冻期，说明在这一天卖出了股票(这里有点费解)。
dp[i][1] = dp[i-1][0] + prices[i]第i天处于非冷冻期未持有股票状态，说明前一天没有做任何操作。
dp[i][2] = max(dp[i-1][1], dp[i-1][2]])
class Solution:
def maxProfit(self, prices):
if not prices:
return 0
n = len(prices)
dp = [[0 for _ in range(3)] for _ in range(n)]
dp[0][0] = - prices[0]
for i in range(1, n):
dp[i][0] = max(dp[i-1][0], dp[i-1][2] - prices[i])
dp[i][1] = dp[i-1][0] + prices[i]
dp[i][2] = max(dp[i-1][1], dp[i-1][2])
return max(dp[n-1][1], dp[n-1][2])
如有疑问或建议，欢迎评论区留言~
