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

1. 题目描述

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​

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

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

2. 思路

1. 思路一
   • DFS
   • 假设买了i，那么从后面找出一个>i的j，计算收益
   • 继续j+2

• DFS+缓存

3. 实现

3.1. DFS+缓存（超时）

func maxProfit(prices []int) int {
    memo := make(map[int]int, 0)
    return maxProfitDFS(prices, 0, memo)
}

func maxProfitDFS(prices []int, index int, memo map[int]int) int {
    profit, ok := memo[index]
    if ok {
        return profit
    }

    if index >= len(prices) {
        return 0
    }

    profit = 0
    for i := index; i < len(prices)-1; i++ {
        buy := prices[i]
        for j := i+1; j < len(prices); j++ {
            sell := prices[j]
            if sell > buy {
                profit = max(profit, sell-buy+maxProfitDFS(prices, j+2, memo))
            }
        }
    }
    memo[index] = profit
    return profit
}

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

3.2. DFS+缓存

const (
    OptBuy = 0
    OptSell = 1
)

func maxProfit(prices []int) int {
	memo := make(map[string]int, 0)
	return maxProfitDFS(prices, 0, OptBuy, memo)
}

//第index天执行opt操作获得的收益
func maxProfitDFS(prices []int, index int, opt int, memo map[string]int) int {
	if index >= len(prices) {
		return 0
	}

	if profit, ok := memo[getKey(index, opt)]; ok {
		return profit
	}

	//定义三个变量，分别记录[不动]、[买]、[卖]
	a, b, c := 0, 0, 0
	//保持不动
	a = maxProfitDFS(prices, index+1, opt, memo)
	//卖出
	if opt == OptSell {
		//卖出后有一天的冷冻期，那么需要index+2才能执行操作
		b = maxProfitDFS(prices, index+2, OptBuy, memo) + prices[index]
	//买入
	} else {
		//买入后没有冷冻期，那么index+1就能执行操作
		c = maxProfitDFS(prices, index+1, OptSell, memo) - prices[index]
	}

	//最终结果就是三个变量中的最大值
	profit := Max(a, b, c)
	memo[getKey(index, opt)] = profit
	return profit
}

func getKey(index int, opt int) string{
	return fmt.Sprintf("%v:%v", index, opt)
}

func Max(data ...int) int {
	max := data[0]
	for i := 1; i < len(data); i++ {
		if data[i] > max {
			max = data[i]
		}
	}
	return max
}

4. 参考

• 309. 最佳买卖股票时机含冷冻期 - 力扣（LeetCode）