T+2规则
本题意为用户在卖出之后需要休息一天才能进行操作，那么在本题中用户是存在有三个状态，未持有（unhold）、持有（hold）、休息（cooldown）这三种，这三种状态的状态转化图为：
其对应的状态转换函数为:
unhold[i] = max(unhold[i - 1], cooldown[i - 1]); // Stay at s0, or rest from s2
hold[i] = max(hold[i - 1], unhold[i - 1] - prices[i]); // Stay at s1, or buy from s0
cooldown[i] = hol[i - 1] + prices[i]; // Only one way from s1
代码为:
package wx.algorithm.op.dp.stock;
/**
* Created by apple on 16/8/21.
*/
public class StockWithCoolDown {
public int maxProfit(int[] prices) {
//判断日期长度是否大于1
if (prices.length <= 1) {
return 0;
}
//构建三个状态数组
int[] unhold = new int[prices.length];
int[] hold = new int[prices.length];
int[] cooldown = new int[prices.length];
unhold[0] = 0;
hold[0] = -prices[0];
cooldown[0] = Integer.MIN_VALUE;
for (int i = 1; i < prices.length; i++) {
unhold[i] = Math.max(unhold[i - 1], cooldown[i - 1]);
hold[i] = Math.max(hold[i - 1], unhold[i - 1] - prices[i]);
cooldown[i] = hold[i - 1] + prices[i];
}
return Math.max(unhold[prices.length - 1],cooldown[prices.length - 1]);
}
}
