倒数9
目录
309.最佳买卖股票时机含冷冻期
在动态规划：122.买卖股票的最佳时机II中有两个状态，持有股票后的最多现金，和不持有股票的最多现金。
动规五部曲，分析如下：
1、确定dp数组以及下标的含义
dp[i][j]，第i天状态为j，所剩的最多现金为dp[i][j]。
其实本题很多同学搞的比较懵，是因为出现冷冻期之后，状态其实是比较复杂度，例如今天买入股票、今天卖出股票、今天是冷冻期，都是不能操作股票的。 具体可以区分出如下四个状态：
- 状态一：买入股票状态（今天买入股票，或者是之前就买入了股票然后没有操作）
- 卖出股票状态，这里就有两种卖出股票状态
- 状态二：两天前就卖出了股票，度过了冷冻期，一直没操作，今天保持卖出股票状态
- 状态三：今天卖出了股票
- 状态四：今天为冷冻期状态，但冷冻期状态不可持续，只有一天！
j的状态为：
- 0：状态一
- 1：状态二
- 2：状态三
- 3：状态四
很多题解为什么讲的比较模糊，是因为把这四个状态合并成三个状态了，其实就是把状态二和状态四合并在一起了。
从代码上来看确实可以合并，但从逻辑上分析合并之后就很难理解了，所以我下面的讲解是按照这四个状态来的，把每一个状态分析清楚。
注意这里的每一个状态，例如状态一，是买入股票状态并不是说今天已经就买入股票，而是说保存买入股票的状态即：可能是前几天买入的，之后一直没操作，所以保持买入股票的状态。
2、确定递推公式
达到买入股票状态（状态一）即：dp[i][0]，有两个具体操作：
- 操作一：前一天就是持有股票状态（状态一），dp[i][0] = dp[i - 1][0]
- 操作二：今天买入了，有两种情况
- 前一天是冷冻期（状态四），dp[i - 1][3] - prices[i]
- 前一天是保持卖出股票状态（状态二），dp[i - 1][1] - prices[i]
所以操作二取最大值，即：max(dp[i - 1][3], 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] = max(dp[i - 1][1], dp[i - 1][3]);
达到今天就卖出股票状态（状态三），即：dp[i][2] ，只有一个操作：
- 操作一：昨天一定是买入股票状态（状态一），今天卖出
即：dp[i][2] = dp[i - 1][0] + prices[i];
达到冷冻期状态（状态四），即：dp[i][3]，只有一个操作：
- 操作一：昨天卖出了股票（状态三）
dp[i][3] = dp[i - 1][2];
综上分析，递推代码如下：
dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3], dp[i - 1][1]) - prices[i]);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);
dp[i][2] = dp[i - 1][0] + prices[i];
dp[i][3] = dp[i - 1][2];
3、dp数组如何初始化
这里主要讨论一下第0天如何初始化。
如果是持有股票状态（状态一）那么：dp[0][0] = -prices[0]，买入股票所剩现金为负数。
保持卖出股票状态（状态二），第0天没有卖出dp[0][1]初始化为0就行，
今天卖出了股票（状态三），同样dp[0][2]初始化为0，因为最少收益就是0，绝不会是负数。
同理dp[0][3]也初始为0。
4、确定遍历顺序
从递归公式上可以看出，dp[i] 依赖于 dp[i-1]，所以是从前向后遍历。
5、举例推导dp数组
以 [1,2,3,0,2] 为例，dp数组如下：
最后结果是取 状态二，状态三，和状态四的最大值，不少同学会把状态四忘了，状态四是冷冻期，最后一天如果是冷冻期也可能是最大值。
func maxProfit(prices []int) int {
n := len(prices)
if n < 2 {
return 0
}
dp := make([][]int, n)
for i:=0;i<n;i++{
dp[i] = make([]int, 4)
}
// 初始化问题
// 持有股票状态
dp[0][0] = -prices[0]
// dp[0][1] 第0天没卖出去呢初始化为0(今天是两天前就卖出股票且度过冷冻期)
// dp[0][2] 第0天没卖出去呢初始化为0（今天是卖出股票状态）
// dp[0][3] 第0天都没卖呢没有冷冻期呢初始化为0
for i:=1;i<n;i++{
// dp[i][0]：买入股票状态
//前一天就这状态， 前一天是保持卖出状态 ，前一天是冷冻期
dp[i][0] = max(dp[i-1][0], max(dp[i-1][1]-prices[i], dp[i-1][3]-prices[i]))
// dp[i][1]：股票已卖，冷冻期已过，保持股票卖出状态
// 前一天就这状态， 前一天是冷冻期。
dp[i][1] = max(dp[i-1][1], dp[i-1][3] )
// dp[i][2]：今天要卖股票状态。
// 前一天是买入状态
dp[i][2] = dp[i-1][0] + prices[i] // 这里说的前一天买入并不一定是前一天买入的，可能是前前前一天买入然后它一直保持状态不变。
// dp[i][3]：今天是冷冻期状态。
// 冷冻期只能通过前一天是卖出状态得到。
dp[i][3] = dp[i-1][2]
}
// 最后结果应该是取 (今天是两天前就卖出股票且度过冷冻期) 、 （今天是卖出股票状态）、(今天是冷冻期状态) 这三个的最大值呢
return max(dp[n-1][1],max(dp[n-1][2],dp[n-1][3]))
}
func max(a, b int) int {
if a > b {
return a
}
return b
}相对于动态规划：122.买卖股票的最佳时机II，本题只需要在计算卖出操作的时候减去手续费就可以了，代码几乎是一样的。
唯一差别在于递推公式部分，所以本篇也就不按照动规五部曲详细讲解了，主要讲解一下递推公式部分。
这里重申一下dp数组的含义：
dp[i][0] 表示第i天持有股票所省最多现金。 dp[i][1] 表示第i天不持有股票所得最多现金
如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来
- 第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]
- 第i天买入股票，所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即：dp[i - 1][1] - prices[i]
所以：dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
在来看看如果第i天不持有股票即dp[i][1]的情况， 依然可以由两个状态推出来
- 第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]
- 第i天卖出股票，所得现金就是按照今天股票价格卖出后所得现金，注意这里需要有手续费了即：dp[i - 1][0] + prices[i] - fee
所以：dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
本题和动态规划：122.买卖股票的最佳时机II的区别就是这里需要多一个减去手续费的操作。
以上分析完毕，Go代码如下：
func maxProfit(prices []int, fee int) int {
n := len(prices)
dp := make([][2]int,n)
dp[0][0] = -prices[0]
// dp[i][0]: 第i天持有股票时候的现金
// dp[i][1]: 第i天不持有股票时候的现金
for i:=1;i<n;i++{
dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i] - fee)
}
// 返回最终不持有股票时的现金。
return dp[n-1][1]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}自己总结去吧你。