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

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

  • 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
  • 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
  1. //二维动规  基础版，时空都是On
  2. func maxProfit(prices []int) int {
  3.     // 要定义dp的len, 如果为1也不行
  4.     if len(prices) < 2 {
  5.         return 0
  6.     }
  8.     dp := make([][2]int, len(prices))
  9.     dp[0][0] = 0
  10.     dp[0][1] = -prices[0]
  11.     dp[1][0] = maxInt(dp[0][0], dp[0][1] + prices[1])
  12.     dp[1][1] = maxInt(dp[0][0] - prices[1], dp[0][1])
  14.     for i := 2; i < len(prices); i++ {
  15.         dp[i][0] = maxInt(dp[i - 1][0], dp[i - 1][1] + prices[i])
  16.         dp[i][1] = maxInt(dp[i - 1][1], dp[i - 2][0] - prices[i])
  17.     }
  19.     return dp[len(prices) - 1][0]
  20. }
  22. func maxInt(x, y int) int {
  23.     if x > y {
  24.         return x
  25.     }
  26.     return y
  27. }
//滚动数组，空间优化O1
func maxProfit(prices []int) int {
    n := len(prices)

    if n < 1 {
        return 0
    }

    f0, f1, f2 := -prices[0], 0, 0          // f0: 目前持有股票，累计收益，f1: 目前不持有任何股票，处于冷冻期，累计收益 f2: 目前不持有股票，并且不处于冷冻期，累计收益

    for i := 1; i < n; i++ {
        newf0 := Max(f0, f2-prices[i]) // 第i-1天买入和第i天买入最大收益
        newf1 := f0+prices[i] // 第i天冷冻
        newf2 := Max(f2, f1) // 第i-1天卖出和第i-1天处于冷冻期，第i天不做任何操作
        f0, f1, f2 = newf0, newf1, newf2
    }
    return Max(f1, f2)
}
func Max(a, b int) int {
    if a > b {
        return a
    }
    return b
}