309.md

Best Time to Buy and Sell Stock with Cooldown

题目

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

Example: Input: [1,2,3,0,2] Output: 3 Explanation: transactions = [buy, sell, cooldown, buy, sell]

总结

    这题的解题思路和1186很像。这类dp问题的特点是："当前可以做什么选择，这些选择依赖于什么条件, 这些条件就是子问题的一些状态或者结果"
对于数组[x1,x2,x3...xm]结果res,对于加入新的一天股价为xn。那么xn可以处于三种状态cooldown,sell,buy。而这三种状态又依赖于前面的状态。
如果当前为cooldown则前一个状态可以是cooldown或者sell或者buy。
如果当前为sell则前一个状态必然是buy->cooldown.cooldown可以是多个但是必须得有buy才有sell。
如果当前为buy则前一个状态必须是cooldown， 其他状态都不行，sell之后必须是cooldown。

对于例子[1,2,3,0,2] cool[i]表示当i天状态是cooldown的最大受益，buy[i]表示当i天状态是buy的最大受益，sell[i]表示当i天状态是选择sell的最大受益(也可能不卖出)
cool[i] = max(cool[i-1], buy[i-1], sell[i-1]), buy[i] = cool[i-1], sell[i] = max(buy[i-k] + prices[i]-prices[i-k], sell[i-1]) k在区间[0,i-1]

cool [0,0,1,2,2]

buy  [0,0,0,1,2]

sell [0,1,2,2,3]

所以结果为3

优化：
由于cool, sell只用了当前状态，所以可以用一个变量. 在内部循环中需要遍历buy数组，但是这个遍历可以用一个cache变量优化
当前的prices[i] - prices[i-k] + buy[i-k] --> prices[i] - (prices[i-k]-buy[i-k]) 只要保存prices[i-k]-buy[i-k]的最小值cache就可以得到最大的cache值。

代码

func maxProfit(prices []int) int {
    if len(prices) == 0 {
        return 0
    }
    res, cooldown, buy, cache := 0, 0, 0, prices[0]
    for i := 1; i < len(prices); i++ {
        buy = cooldown
        cooldown = max(res, cooldown)
        if res < prices[i] - cache {
            res = prices[i] - cache
        }
        if prices[i] - buy < cache {
            cache = prices[i] - buy
        }
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}