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)
在决定是否sell的时候，想到sell了之后要cool down，不能买进，所以global最优解可能并不是一直track local的最优解能得到的。例如[1,3,4,0,2]，在3处sell了，0处还可以买进，总利润4。在4处sell，就不能再获得新的利润了，总利润是3. 所以比较明显用DP来做。
buy[i] = max(rest[i-1]-price, buy[i-1])
sell[i] = max(buy[i-1]+price, sell[i-1])
rest[i] = max(sell[i-1], buy[i-1], rest[i-1])
注意到buy[i] <= rest[i], rest[i] <= sell[i]，所以rest[i] = sell[i-1]. 所以公式变为：
buy[i] = max(sell[i-2] – price, buy[i-1])
sell[i] = max(buy[i-1] + price, sell[i-1])