代码随想录day41 || 121 买卖股票最佳时机，122 买卖股票最佳时机||，123 买卖股票最佳时机|||

121 买卖股票最佳时机

func maxProfit(prices []int) int {
	// dp五部曲
	// 1 dp数组以及下标含义 dp[i][0] 表示第i天持有股票  dp[i][1] 表示第i天不持有
	// 2 递推公式，dp[i][0] = max(dp[i-1][0], 0-price[i])
	//           dp[i][1] = max(dp[i-1][1], dp[i-1][0]+price[i])
	// 初始化，如果第0天持有就是dp[0][0] = -price[0], 不持有就是dp[0][1] = 0
	// 遍历prices
	// 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 - prices[0]
	dp[0][1] = 0
	for i:=1; i<len(prices); i++ {
		dp[i][0] = max(dp[i-1][0], 0-prices[i])
		dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i])
	}
	//fmt.Println(dp)
	return dp[len(prices)-1][1]
}

122 买卖股票最佳时机||

func maxProfit(prices []int) int {
	// dp五部曲
	// 1 dp数组以及下标含义 dp[i][0] 表示第i天持有股票  dp[i][1] 表示第i天不持有
	// 2 递推公式，dp[i][0] = max(dp[i-1][0], dp[i-1][1]-price[i]) // 和买卖1区别在于可能非首次购买了，此时我们已经有部分利润，不再是0-price
	//           dp[i][1] = max(dp[i-1][1], dp[i-1][0]+price[i])
	// 初始化，如果第0天持有就是dp[0][0] = -price[0], 不持有就是dp[0][1] = 0
	// 遍历prices
	// 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 - prices[0]
	dp[0][1] = 0
	for i:=1; 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-1][0] + prices[i])
	}
	//fmt.Println(dp)
	return dp[len(prices)-1][1]
}

买卖股票最佳时机|||

func maxProfit(prices []int) int {
	// 难点在于有四个状态
	// dp[i][0] 表示第一次持有 = max(dp[i-1][0], 0-price[i])
	// dp[i][1] 表示第一次不持有 = max(dp[i-1][1], dp[i-1][0]+price[i])
	// dp[i][2] 表示第二次持有 = max(dp[i-1][2], dp[i-1][1]-price[i]) // 此时已经一次买卖，所以手上现金可能不是0
	// dp[i][3] 表示第二次不持有 = max(dp[i-1][3], dp[i-1][2]+price[i])
	// 初始化 dp[0][0] = -price[0] , dp[0][1]=0 , dp[0][2] = -price[0] , dp[0][3] = 0

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

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