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]
题目大意：
得到买卖股票获取的最大收益。
解法：
采用DP的方法来解决。
1.定义数组的状态
buy[i]代表在第i天最后一个Action是买的最大获益（但是这个Action可能不是发生在第i天，有可能是第i天之前发生的，有可能是在第i-1,i-2,i-3发生的）
sell[i]代表在第i天最后一个Action是卖的最大获益，所以方法的返回应该是sell[n-1]，因为最后一个Action肯定是以卖结束的，而不是以买结束的。
2.定义数组的变化
第i天的买事件要么延续前面i-1的买事件（在当天不做买卖），要么是第i-2天是以卖结束的，第i天开始买。
第i天的卖事件要么延续前面i-1的卖事件（在当天不做买卖），要么是第i-1天是以买结束的，第i天开始卖。
可以得到方程式如下：
buy[i] = Math.max(buy[i - 1], sell[i - 2] - prices[i]); sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);
3.优化空间负载度
由于buy,sell这两个数组只使用了第i，i-1和i-2这三天的。
所以b0,b1,b2分别代表buy[i],buy[i-1],buy[i-2]，s0,s1,s2分别代表sell[i],sell[i-1],sell[i-2]
可以优化方程式如下：
b0 = Math.max(b1, s2 - prices[i]);s0 = Math.max(s1, b1 + prices[i]);
4.初始化
由于buy事件在第一天的最大的获益，就是将第一天的股票买入，就是-price[0]
而sell事件在第一天的最大获益则是0，因为前面没有股票买入。
java:
class Solution { public int maxProfit(int[] prices) { if (prices.length==0||prices.length==1) return 0; int b0=-prices[0],b1=b0; int s0=0,s1=0,s2=0; for(int i=1;i