LeetCode0309.最佳买卖股票时期含冷冻期 Go语言AC笔记_最佳买卖股票时间含冷冻期

 时间复杂度：O(n)，空间复杂度：O(1)

解题思路

还是动态规划，不过怎么规划是个问题。

这次该题一共会有三种状态：

1. 手上持有股票
2. 手上没股票还被冷冻了
3. 手上没股票但我能买

我们令dp[i]表示第i天结束后我们的收益，注意此处的结束后可以理解为我今日对股票“操作”了一波之后，而“操作”无非是买、卖、摆烂（不动股票）三种。如果我们在第i天买了股票，那么收益就要减去第i天的股票价格，当然如果我们在第i天卖了股票，那么我们的收益就要加上第i天的股票价格。

如果加上三种状态，dp[i][1]就表示第i天结束后状态为①且收益为dp[i]，同理dp[i][2]就表示第i天结束后状态为②且收益为dp[i]，dp[i][3]就表示第i天结束后状态为③且收益为dp[i]。既然是第i天结束后，那么我们也可以将dp[i]后的状态理解为i+1天操作股票前的状态。

这样我们就可以逐个分析第i天结束后的三种状态了：

1、手上持有股票

如果在今日我操作股票之后手上持有股票，那么在今日我可能进行了什么操作呢？没错，可能在前一天结束后我就有股票，然后在今天我摆烂了一天没动股票；也可能今天我刚买股票，所以现在第i天结束我能持有股票。

对于前者，前一天结束的状态对应为①（手上持有股票），且收益为dp[i-1]，那我们今天的收益dp[i]还是dp[i-1]，并且还是保持状态①，因为我们摆烂了呀，没花钱买股票也没赚钱卖股票，对应状态方程为dp[i][1]=dp[i-1][1]；对于后者，前一天结束后的状态为③（手上没股票但我能买），也就是今天我购买股票前的状态为③，且收益为dp[i-1]，那我们今天操作后的收益dp[i]就是dp[i-1]-price[i]，状态变为①，对应状态方程为dp[i][1]=dp[i-1][3]-price[i]。

而我们的目标是追求最大收益，所以二者取较大值即可，状态方程即为dp[i][1]=max(dp[i-1][1],dp[i-1][3]-price[i])

2、手上没股票还被冷冻了

为什么第i天结束后手上没股票还被冷冻了呢？肯定是因为今天我卖股票了触发冷冻机制了呀！

所以前一天结束后的状态一定为①（手上持有股票），也可以理解为今天我卖股票之前的状态为①，当我卖出股票后状态就变为了②，所以状态转移方程为dp[i][2]=dp[i-1][1]+price[i]。

3、手上没股票但我能买

第i天操作股票后我的手上还是没股票并且没被冷冻，那就只有两种情况：一种是我今天又摆烂了，前一天结束后我没有股票我今天过去还是没股票；第二种是我前一天结束后处于冷冻期，而我今天刚好解封但继续摆烂，手里没股票我能买也不买。

对于前者，第i-1天结束后的状态为③（手上没股票但我能买），第i天结束后状态保持③，所以状态转移方程为dp[i][3]=dp[i-1][3]；对于后者，第i-1天结束后的状态为②（手上没股票还被冷冻了），第i天结束后状态变为③，所以状态转移方程为dp[i][3]=dp[i-1][2]。

还是二者取较大值，最终的状态转移方程为dp[i][3]=max(dp[i-1][2],dp[i-1][3])

从三种状态转移方程我们可看出，第i天的收益其实只与第i-1天有关，所以我们还是按照以往滚动数组的方法保存前一天三种状态的收益即可，不必单写dp数组，这样空间复杂度为O(1)。

AC代码

func maxProfit(prices []int) int {
    n:=len(prices)
    //f[i][0]:第i天结束后手上持有股票的收益
    //f[i][1]:第i天结束后手上无股票且会处于冷冻期的收益
    //f[i][2]:第i天结束后手上无股票但不处于冷冻期的收益
    f0,f1,f2:=-prices[0],0,0
    for i:=1;i<n;i++{
        f0,f1,f2=max(f0,f2-prices[i]),f0+prices[i],max(f1,f2)
    }
    return max(f1,f2)
}
func max(i,j int)int{
    if i>j{
        return i
    }
    return j
}

感悟

正如最高赞评论所说，知道DP，但不知道如何DP……