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

题目描述：

给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: prices = [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
示例 2:

输入: prices = [1]
输出: 0

思路:

用动态规划来做，

// dp[0]是持有股票
// dp[1]是在冷静期
// dp[2]是不在冷静期也不持有股票

找出他们的递推公式

dp[i][0] = max(dp[i-1][0], dp[i-1][2]-prices[i]) // 持有股票的最佳策略是上一个价格买或者继续持有
dp[i][1] = dp[i-1][0] + prices[i]。// 冷静期上上一个状态加上卖的钱
dp[i][2] = max(dp[i-1][1], dp[i-1][2])。//不在冷静期的状态最好的情况是选取冷静期和不在冷静期的最大值

代码:

func maxProfit(prices []int) int {
    n := len(prices)
    if len(prices) == 1{
        return 0
    }
    dp := make([][3]int, n)
    // dp[0]是持有股票
    // dp[1]是在冷静期
    // dp[2]是不在冷静期也不持有股票
    dp[0][0] = -prices[0]
    dp[0][1], dp[0][2] = 0,0
    for i:=1;i <len(prices);i++{
        dp[i][0] = max(dp[i-1][0], dp[i-1][2]-prices[i])
        dp[i][1] = dp[i-1][0] + prices[i]
        dp[i][2] = max(dp[i-1][1], dp[i-1][2])
    }
    return max(dp[n-1][2], dp[n-1][1])
    
}

func max(a,b int) int {
    if a>b{
        return a
    }else{
        return b
    }
}

代码效率：

执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：2.3 MB, 在所有 Go 提交中击败了74.08%的用户