309. 最佳买卖股票时机含冷冻期

原题

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

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

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

示例:

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

解题思路1

尝试走出所有路径。利用递归和缓存结果的方式进行优化，并设置结束条件进行约束。可惜，不能通过所有测试，提示超时。

class Solution {
    var cachedResults = [[Int]:Int]()
    
    func maxProfit(_ prices: [Int]) -> Int {
        var dealProfit = 0
        var firstDealEndAt:Int? = nil
        
         // 买，卖，冻；买，卖，冻
        for buyIndex in 0..<prices.count {
            let sellIndexStartAt = buyIndex + 1
            guard sellIndexStartAt < prices.count else {
                return dealProfit
            }
            
            let buyPrice = prices[buyIndex]
            for sellIndex in sellIndexStartAt..<prices.count {
                if let dealEndAt = firstDealEndAt {
                    guard buyIndex < dealEndAt else {
                        break
                    }
                }
                
                let sellPrice = prices[sellIndex]
                if buyPrice < sellPrice {
                    if let endDealAt = firstDealEndAt {
                        if endDealAt > sellIndex {
                            firstDealEndAt = sellIndex
                        }
                    } else {
                        firstDealEndAt = sellIndex
                    }
                    
                    var profit = sellPrice - buyPrice
                    
                    let nextIndex = sellIndex + 2
                    
                    if nextIndex < prices.count {
                        let remainPrices = Array(prices[nextIndex...])
                        let remainProfit:Int = {
                            if let profit = cachedResults[remainPrices] {
                                return profit
                            }
                            
                            let profit = maxProfit(remainPrices)
                            cachedResults.updateValue(profit, forKey: remainPrices)
                            
                            return profit
                        }()
                        
                        profit += remainProfit
                    }
                    
                    dealProfit = max(dealProfit, profit)
                }
            }
        }

        return dealProfit
    }
}

解题思路2

思路2是同时计算每一步的状态。我们知道，针对每一个数据，它可能的状态有3个，即买、卖、等待。如图：

s0[i] = max(s0[i - 1], s2[i - 1]); // 冷却可能是原地等待，也可能是卖完之后强制冷却
s1[i] = max(s1[i - 1], s0[i - 1] - prices[i]); // Stay at s1, or buy from s0 原地等待，或者购买，如果购买，则肯定是从s0状态过来的。
s2[i] = s1[i - 1] + prices[i]; // 卖出获利

最终代码：

class Solution {
    func maxProfit(_ prices: [Int]) -> Int {
        guard !prices.isEmpty else {
            return 0
        }
        
        var s0 = Array<Int>(repeating: 0, count: prices.count)
        var s1 = Array<Int>(repeating: 0, count: prices.count)
        var s2 = Array<Int>(repeating: 0, count: prices.count)
        
        s0[0] = 0
        s1[0] = -prices[0]
        s2[0] = Int.min
        
        for index in 1..<prices.count {
            s0[index] = max(s0[index - 1], s2[index - 1])
            s1[index] = max(s1[index - 1], s0[index - 1] - prices[index])
            s2[index] = s1[index - 1] + prices[index]
        }

        return max(s0.last!, s2.last!) // 最后一步，要么是冷却状态，要么是卖出状态。不可能是买入状态
    }
}

参考资料：

• Share my DP solution (By State Machine Thinking)