最佳买卖股票时机含冷冻期
题目：
每天可以选择可以买入卖出或者继续持有一笔股票，只有卖出之后才能重新买入一笔股票，并且卖出股票之后的第一天处于冷冻期，不能买入股票。问如何才能拿到最大收益？
思路：每一天的收益状态都是依赖于前一天收益状态的。因此可以对每一天分为三种情况：
情况1：持有该笔股票的最大收益，这一笔股票可以是今天买入的，也可以是本来就有的。
情况2：不持有该笔股票并且处于冷冻期的最大收益，也就是昨天卖出了这笔股票。
情况3：不持有该笔股票并且不处于冷冻期的最大收益，昨天可能是冷冻期也可能不是。
可以定义一个二维数组来进行转态转移。
得到如下状态转移方程:
dp[i][0] = max(dp[i-1][0], dp[i][2] - prices[i])
dp[i][1] = dp[i-1][0] + prices[i]
dp[i][2] = max(dp[i-1][2], dp[i-1][1])
func maxProfit(prices []int) int {
days := len(prices)
dp := make([][]int, days)
for i:=0; i b{
return a
}
return b
}
优化空间：
由于每一个状态i都依赖于i-1，故可以使用三个变量来代替就行，不必要开一个数组，可以把空间降到O(1)。
class Solution {
public int maxProfit(int[] prices) {
int x1 = -prices[0] ,x2 =0,x3 =0;
for(int i = 1; i< prices.length; i++){
int y1 = Math.max(x1, x3 - prices[i]);
int y2 = x1 + prices[i];
int y3 = Math.max(x2, x3);
x1 = y1;
x2 = y2;
x3 = y3;
}
return Math.max(x2 , x3);
}
}
总结一下动态规划的解题步骤：
1. 确定dp数组及其下标含义。
2. 求出状态转移方程。
3. dp数组如何初始化。
4. 确定遍历顺序。
