题目：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
思路：
这题一看就是动态规划。把prices数组扫一遍，每天无非4种情况：买入、卖出、冷冻、啥也不干。冷冻期其实也可以视作一种操作。我们要考虑的就是，截至到今天，我的最后一次操作是买、卖还是冷冻时，我到今天的收益最高。于是可以开三个数组buy[]、sell[]、lock[]，buy[i]表示截至第i天，最后一次操作是买入的话，最大的收益是多少。sell[i]和lock[]同理。
于是不难列出状态转移方程：
// 其中buy[i-1]表示截至昨天最后一个操作是买入且今天啥也不干，lock[i-1] - prices[i]表示截至昨天最后一个操作是冷冻且今天买入
buy[i] = max{ buy[i-1] , lock[i-1] - prices[i] } 特殊地，buy[0] = -prices[0]
// buy[i-1] + prices[i]表示截至昨天最后一个操作是买入且今天卖出
sell[i] = buy[i-1] + prices[i]
// 其中lock[i-1]表示截至昨天最后一个操作是冷冻且今天啥也不干，sell[i-1]表示截至昨天最后一个操作是卖出且今天冷冻
lock[i] = max { lock[i-1] , sell[i-1] }
代码：
1 /** 2 * @author yuan 3 * @version 0.1 4 * @date 2019/4/5 5 */ 6 public class Leetcode309 { 7 8 public int maxProfit(int[] prices) { 9 if (prices.length == 0) { 10 return 0; 11 } 12 int[] buy = new int[prices.length]; 13 int[] sell = new int[prices.length]; 14 int[] lock = new int[prices.length]; 15 for (int i = 0; i < prices.length; i++) { 16 buy[i] = Integer.MIN_VALUE; 17 } 18 for (int i = 0; i < prices.length; i++) { 19 if (i == 0) { 20 buy[i] = -prices[i]; 21 } else { 22 buy[i] = Math.max(buy[i - 1], lock[i - 1] - prices[i]); 23 sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]); 24 lock[i] = Math.max(lock[i - 1], sell[i - 1]); 25 } 26 } 27 int result = buy[prices.length - 1]; 28 if (sell[prices.length - 1] > result) { 29 result = sell[prices.length - 1]; 30 } 31 if (lock[prices.length - 1] > result) { 32 result = lock[prices.length - 1]; 33 } 34 return result; 35 } 36 }
优化：
对于每一天的情况，只有上一天的状态对今天有用，因此三个数组可以缩减到长度为2。也可以只用一个变量存储，但在赋值前要注意用临时变量保存一下。
[Leetcode309] 最佳买卖股票时机含冷冻期 动态规划
原文：https://www.cnblogs.com/null-0/p/10660221.html