动态规划 买股票

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]);

}

}