题目

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

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

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

来源：力扣（LeetCode）

Python解法

动态规划解法

具体的解题思路如下：

• 首先计算 prices 的长度 n，如果 n 小于2，那么直接返回0；
• 建立一个长度为 n、初始元素为 [0, 0] 的数组 dp，则可以用 dp[i][0] 来选取数组的数组的元素，dp[][] 这两个框中前面代表天数，后面代表是否持有股票，对应的值就是对应的利润最大值；
• dp[i][0] 代表第 i-1 天不持股或者第 i-1 天持股然后第 i 天卖出；
• dp[i][1] 有所不同，按照正常的理解应该是第 i-1 天持股或者第 i-1 天不持股然后第 i 天持股，但是这里有一个冷冻期，是需要隔一天的，因此如果你在第 i-1 天不持股那么在第 i-2 天一定也不能持股，否则第 i-2 天持股在第 i-1 天不持股说明在第 i-1 天卖出，那么第 i 天是冷冻期，是不允许持股的。因此对于 dp[i][1] 来说，第 i-1 天如果不持股，那么第 i-2 天也不应该持股，这样将 第 i-1 天作为冷冻期，第 i 天才能持股；
• 最后返回dp[-1][0]因为不持股利润是要大于等于持股的。

代码如下：

def maxProfit(self, prices: List[int]) -> int:
    n = len(prices)
    if n < 2: return 0
    dp = [[0,0] for i in range(n)]   #dp的初始化

    dp[0][0] = 0     #第0天不持股自然就为0了
    dp[0][1] = -prices[0]   #第0天持股，那么价格就是-prices[0]了
    #第1天不持股，要么第0天就不持股，要么就是第0天持股，然后第1天卖出
    dp[1][0] = max(dp[0][0],dp[0][1]+prices[1]) 
    #第一天持股，要么就是第0天就持股了，要么就是第0天不持股第1天持股
    dp[1][1] = max(dp[0][1],dp[0][0]-prices[1])
    
    for i in range(2,n):
        dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i])
        dp[i][1] = max(dp[i-1][1],dp[i-2][0]-prices[i])
    return dp[-1][0]