代码随想录day42 || 188 买卖最佳时机IV，309 买卖最佳时机含冷冻期，714 买卖最佳时机含手续费

188 买卖最佳实际IV(k次机会交易)

func maxProfit(k int, prices []int) int {
	// 此题相比买卖两次条件改为买卖k次，所以dp数组行树需要增加为k*2 + 1
	// dp[i][j]表示 if j%2 == 1 第i天第j/3次持有股票获得的收益， j%2==0 第i天第j/2 次不持有获得的收益
	// j%2==1 dp[i][j] = -price[0] ;   j%2==0 dp[i][1] = 0
	// 遍历股票
	// print

	if len(prices) == 1{
		return 0
	}

	var dp = make([][]int, len(prices))
	for idx, _ := range dp {
		dp[idx] = make([]int, k*2+1)
		if idx == 0 {   // 初始化第0天
			for j, _ := range dp[idx] {
				if j % 2 == 1 {
					dp[idx][j] = -prices[0]
				}
			}
		}
	}


	for i:=1; i<len(prices); i++ {
		for j:=1; j<2*k+1; j++{
			if j % 2 == 0 {
				dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + prices[i])
			}else {
				dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] - prices[i])
			}
		}
	}
	//fmt.Println(dp)
	return dp[len(prices)-1][2*k]
}

309 买卖最佳时机含冷却期

func maxProfit(prices []int) int {
	// dp[i][1] 含义第i天持有    dp[i][0] 含义第i天不持有的状态
	// 因为有冷却所以递推公式略有变化，之前的递推依赖前一天持有不持有，需要调整
	// dp[i][0] = max(dp[i-1][0], dp[i-1][1] + price[i]) 今天不持有，可能是昨天也不持有的最大金额，比较 昨天持有今天卖出
	// dp[i][1] = max(dp[i-1][1], dp[i-2][0] - price[i]) 今天持有，可能是昨天持有，或者今天买入（买入条件是前2天不持有才行，因为冷却1天）
	// dp[0][0] = 0 , dp[0][1] = 0-price[0], dp[1][0] = max(dp[0][0], dp[0][1] + price[1]), dp[1][1] = max(-price[1], -price[2])
	if len(prices) == 1{
		return 0
	}
	if len(prices) == 2{
		if prices[1] > prices[0]{
			return prices[1] - prices[0]
		}
		return 0
	}
	var dp = make([][]int, len(prices))
	for idx, _ := range dp {
		dp[idx] = make([]int, 2)
	}
	dp[0][0] = 0
	dp[0][1] = -prices[0]
	dp[1][0] = max(0, -prices[0] + prices[1])
	dp[1][1] = max(-prices[0], -prices[1])

	for i:=2; i<len(prices); i++ {
		dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
		dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])
	}
	//fmt.Println(dp)
	return dp[len(prices)-1][0]
}

714 买卖最佳时机含手续费

func maxProfit(prices []int, fee int) int {
	// 本质上买卖多次，每次多了个手续费，递推公式有所变化
	// dp[i][0] 第i天不持有股票最大收益  dp[i][1] 第i天持有股票最大收益
	// dp[i][0] = max(dp[i-1][0], dp[i-1][1] + price[i] - fee) // 昨天不持有 对比 昨天持有今天卖出，卖出需要扣手续
	// dp[i][1] = max(dp[i-1][1], dp[i-1][0] = price[i]) // 昨天持有 对比 昨天不持有今天买入，买入无手续费用
	// dp[0][0] = 0  dp[0][1] = -price[0]
	// 遍历price
	// print
	if len(prices) == 1{
		return 0
	}

	var dp = make([][]int, len(prices))
	for idx, _ := range dp {
		dp[idx] = make([]int, 2)
	}
	dp[0][0] = 0
	dp[0][1] = -prices[0]

	for i:=1; i<len(prices); i++ {
		dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i] - fee)
		dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
	}
	//fmt.Println(dp)
	return dp[len(prices)-1][0]

}