Leetcode 309：最佳买卖股票时机含冷冻期（最详细的解法！！！）

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

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

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

示例:

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

解题思路

Leetcode 121：买卖股票的最佳时机（最详细的解法！！！）

Leetcode 122：买卖股票的最佳时机II（最详细的解法！！！）

Leetcode 123：买卖股票的最佳时机III（最详细的解法！！！）

这是股票系列问题中目前来看最难的一个，不过有了前面几个问题的思路，这个问题求解起来非常容易。首先，我们看到问题中提到了三种状态buy、sell和cooldown，那么我们脑中的第一个想法就是通过动态规划来解

如果我们index:i天为冷冻期，那么只能说明index:i-1天卖掉了股票，那么i天的收益和i-1天是一样的

• cooldown[i]=sell[i-1]

如果我们考虑index:i天卖出，要求利润最大的话。一种情况是index:i-1当天买入了股票，另一种情况是index:i-1之前就持有股票，index:i-1天也可以卖出，那么我们就需要考虑index:i-1卖出更好呢？还是index:i卖出更好呢？

• sell[i]=max(sell[i-1], buy[i-1]+prices[i])

如果我们考虑index:i天买入，要求利润最大的话。一种情况是index:i-1天是冷冻期，另一种情况是index:i-1天不是冷冻期，也就是index:i-1天也可以买入，那么我们就需要考虑index:i-1买入更好呢？还是index:i买入更好呢？

• buy[i]=max(buy[i-1], cooldown[i-1]-prices[i])

我们第一天不可能卖出或者冻结，那么这两个sell[0]=0 cooldown[0]=0，但是我们第一天可以买入啊，所以buy[0]=-prices[0]。

class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """  
        if not prices:
            return 0

        len_prices = len(prices)
        buy, sell, cooldown = [0]*len_prices, [0]*len_prices, [0]*len_prices
        buy[0] = -prices[0]
        for i in range(1, len_prices):
            cooldown[i] = sell[i-1]
            sell[i] = max(sell[i-1], buy[i-1] + prices[i])
            buy[i] = max(buy[i-1], cooldown[i-1] - prices[i])
        return sell[-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

实际上只需要O(1)的空间复杂度就够了。

class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """  
        if not prices:
            return 0

        len_prices = len(prices)
        buy, sell, cooldown = -prices[0], 0, 0
        for i in range(1, len_prices):
            pre_sell = sell
            sell = max(sell, buy + prices[i])
            buy = max(buy, cooldown - prices[i])
            cooldown = pre_sell
        return sell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

当然我们也应该思考一下怎么通过递归去解这个问题。我们定义一个新的方程_maxProfit(index, flag)，index表示哪一天，而flag表示我们那天是什么状态（持有股票还是不持有股票），整个函数的意思是[index, len(prices)]这个区间内的最大收益。

我们考虑第index:i天持有股票的话，那么考虑当天卖和不卖哪个收益高。

• max(_maxProfit(i+1, 'have'), _maxProfit(i+1, 'cooldown')) + prices[i] - prices[i-1]

我们考虑第index:i天不持有股票的话，那么考虑当天买和不买哪个收益高。

• max(_maxProfit(i+1, 'dhave'), _maxProfit(i+1, 'have'))

当第index:i天冻结的话，我们index:i+1天一定不会持有股票的。

• _maxProfit(i+1, 'dhave')

我们通过这个可以很快速的写出代码

class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """  
        if not prices:
            return 0

        return self._maxProfit(prices, 0, 'dhave')
        
    def _maxProfit(self, prices, i, flag):
        if i == len(prices):
            return 0

        if flag == 'dhave':
            return max(self._maxProfit(prices, i + 1, 'dhave'), \
                        self._maxProfit(prices, i + 1, 'have'))
        elif flag == 'have':
            return max(self._maxProfit(prices, i + 1, 'have'), \
                        self._maxProfit(prices, i + 1, 'cooldown')) + prices[i] - prices[i-1]
        else:
            return self._maxProfit(prices, i + 1, 'dhave')
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

我们同样可以通过记忆化搜索的方式来优化这个问题。

class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """  
        if not prices:
            return 0

        mem = dict()
        return self._maxProfit(prices, 0, 'dhave', mem)
        
    def _maxProfit(self, prices, i, flag, mem):
        if i == len(prices):
            return 0

        if (i, flag) in mem:
            return mem[(i, flag)]

        if flag == 'dhave':
            mem[(i, flag)] = max(self._maxProfit(prices, i + 1, 'dhave', mem), \
                        self._maxProfit(prices, i + 1, 'have', mem))
        elif flag == 'have':
            mem[(i, flag)] = max(self._maxProfit(prices, i + 1, 'have', mem), \
                        self._maxProfit(prices, i + 1, 'cooldown', mem)) + prices[i] - prices[i-1]
        else:
            mem[(i, flag)] = self._maxProfit(prices, i + 1, 'dhave', mem)
        
        return mem[(i, flag)]    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

至此这个问题就被我们完全解决。

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题，希望大家指出！！！