LeetCode 309. 最佳买卖股票时机含冷冻期

题目链接：309. 最佳买卖股票时机含冷冻期

思路：使用动规五部曲分析：

1. 确定dp数组及其下标的含义
   我们在第 i 天会遇到以下4种情况：

   • 买入股票或之前买入股票并维持现状
   • 卖出股票且已经过了冷冻期
   • 卖出股票且没过冷冻期（即今天刚卖出股票）
   • 今天为冷冻期

   所以我们的dp状态可以由一个长度为4的列表来保存。

2. 确定递推公式
   在第 i 天遇到这支股票后，我们共有两种状态（持有股票或未持有股票），且有两种选择（买或者不买），而上述的4种dp数组的状态的递推公式为：
   $dp[i][0]=max(dp[i-1][0],max(dp[i-1][1]-prices[i],dp[i-1][3]-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数组初始化
   如果在第一天买入股票，那一定就花费了第一支股票的价钱，为-prices[0]，所以将dp[i][0]初始化为-prices[0]，其余状态初始化为0。

4. 确定遍历顺序
   从前向后遍历。

5. 打印状态一、二、三中的较大者即可。

go版本：

func maxProfit(prices []int) int {
    
      
    n := len(prices)
    if n < 2 {
    
      
        return 0
    }

    dp := make([][]int, n)
    for i := range dp {
    
      
        dp[i] = make([]int, 4)
    }
    dp[0][0] = -prices[0]
    
    for i := 1; i < n; i++ {
    
      
        dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][1] - prices[i], dp[i - 1][3] - 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]
    }
    
    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
}

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

LeetCode 714. 买卖股票的最佳时机含手续费

题目链接：714. 买卖股票的最佳时机含手续费

思路：与122.买卖股票的最佳时机II这篇博客的思路一致，就在完成一次买卖股票的时候扣除一次手续费即可。

go版本：

func maxProfit(prices []int, fee int) int {
    
      
    n := len(prices)
    dp := make([][]int, n)
    for i:=0; i<n; i++ {
    
      
        dp[i] = make([]int, 2)
    }
    dp[0][0] -= prices[0]
    dp[0][1] = 0

    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], prices[i] + dp[i - 1][0]-fee)
    }

    return dp[n-1][1]
}

func max(i, j int) int {
    
      
    if i > j {
    
      
        return i
    } else {
    
      
        return j
    }
}

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