网站建设技术外包百度seo公司
309.最佳买卖股票时机含冷冻期
1. 确定dp数组（dp table）以及下标的含义
dp[i][j]，第i天状态为j，所剩的最多现金为dp[i][j]。
2. 确定递推公式
拆分卖出股票状态是因为冷冻期前一天一定是具体卖出股票状态。
状态一 dp[i][0]：持有股票状态（今天买入股票，或者是之前就买入了股票然后没有操作，一直持有）
dp[i-1][0]
dp[i-1][3] - prices[i]（冷冻期后买入），dp[i-1][1] - prices[i]（买入前一天保持卖出股票状态）
dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3], dp[i - 1][1]) - prices[i]);不持有股票状态，这里就有两种卖出股票状态
状态二 dp[i][1]：保持卖出股票的状态（两天前就卖出了股票，度过一天冷冻期。或者是前一天就是卖出股票状态，一直没操作）
dp[i-1][1]
dp[i-1][3]
dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);
状态三 dp[i][2]：今天具体卖出股票（前一天一定是持有股票状态才能卖）
dp[i-1][0] + prices[i]
dp[i][2] = dp[i - 1][0] + prices[i];状态四 dp[i][3]：今天为冷冻期状态，但冷冻期状态不可持续，只有一天！
dp[i-1][2] （前一天为具体卖出股票状态）
dp[i][3] = dp[i - 1][2];3. dp数组如何初始化
如果是持有股票状态（状态一）那么：dp[0][0] = -prices[0]，一定是当天买入股票。
dp[0][1] = ？
由于状态本身为非法状态。我们看递推公式中需要把它初始化成多少，就把它初始化成多少。
(1)用到了dp[0][1]：
dp[i][0] = dp[i - 1][1] - prices[i]; (1)
Subsitutde i=1 into (1)
dp[1][0] = dp[0][1] - prices[1]; 第0天状态1初始化为0
dp[0][1] 初始化为0
让递推公式从第一天合理推导下去
同理：dp[0][2] = 0
dp[0][3] = 0 // 第0天就是冷冻期状态不合法
4. 确定遍历顺序
从前往后遍历
for (int i = 1; i < prices.size(); i++) {持有股票的状态，此时手头现金一定不是最大的。最后一天的状态1、2、3都有可能是最大值。
最后结果：最后一天手头最大现金 max(dp[price.size()-1][1], dp[price.size()-1][2], dp[price.size()-1])[3])
5. 举例推导dp数组
