代码随想录算法训练营第四十一天|买卖股票专题：121. 买卖股票的最佳时机、122.买卖股票的最佳时机II、123.买卖股票的最佳时机III

动规五部曲牢记于心

        1、确定好dp[j]数组，以及下标含义

        2、推导出dp[j]公式

        3、初始化，关键dp[0][0]、dp[0][1]，第i天，后面的01表示状态：持有、不持有

        4、确定遍历顺序：

        如果求组合问题，不考虑排序顺序，先遍历物品，再遍历背包；

        求排序问题，考虑前后顺序，先遍历背包，再遍历物品。

        5、打印dp数组，debug

121. 买卖股票的最佳时机【一次买卖一只股票】

贪心方法：因为股票就买卖一次，那么贪心的想法很自然就是取最左最小值，取最右最大值，那么得到的差值就是最大利润。

dp[i][0] 表示第i天持有股票所得最多现金 

dp[i][1] 表示第i天不持有股票所得最多现金

如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来

• 第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]
• 第i天买入股票，所得现金就是买入今天的股票后所得现金即：-prices[i]

那么dp[i][0]应该选所得现金最大的，所以dp[i][0] = max(dp[i - 1][0], -prices[i]);

如果第i天不持有股票即dp[i][1]， 也可以由两个状态推出来

• 第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]
• 第i天卖出股票，所得现金就是按照今天股票价格卖出后所得现金即：prices[i] + dp[i - 1][0]

同样dp[i][1]取最大的，dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);

dp[0][0] -= prices[0]、dp[0][1] = 0

func maxProfit(prices []int) int {
    // minPrice := math.MaxInt64
    // result := 0
    // for _, price := range prices {
    //     minPrice = min(minPrice, price)
    //     result = max(result, price - minPrice)
    // }
    // return result

    if len(prices) == 0 {
        return 0
    }
    dp := make([][]int, len(prices))
    for i := 0; i < len(prices); i++ {
        dp[i] = make([]int, 2)
    }
    dp[0][0] = -prices[0]
    dp[0][1] = 0
    for i := 1; i < len(prices); i++ {
        dp[i][0] = max(dp[i - 1][0], -prices[i])
        dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i])
    }
    return dp[len(prices) - 1][1]
}

122.买卖股票的最佳时机II【多次买卖一只股票】

• dp[i][0] 表示第i天持有股票所得现金。
• dp[i][1] 表示第i天不持有股票所得最多现金

// 方法一、贪心
// func maxProfit(prices []int) int {
//     result := 0
//     for i := 1; i < len(prices); i++ {
//         result += max(0, prices[i] - prices[i - 1])
//     }
//     return result
// }

// 方法二、动态规划
func maxProfit(prices []int) int {
    if len(prices) == 0 {
        return 0
    }
    dp := make([][]int, len(prices))
    for i := 0; i < len(prices); i++ {
        dp[i] = make([]int, 2)
    }
    dp[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[][0]表示持有股票
        dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i])  // dp[][1] 表示不持有股票
    }
    return dp[len(prices) - 1][1]
}

123.买卖股票的最佳时机III【2次买卖股票】

一天一共就有五个状态，

0.没有操作 （其实我们也可以不设置这个状态）

1.第一次持有股票

2.第一次不持有股票

3.第二次持有股票

4.第二次不持有股票

dp[i][j]中 i表示第i天，j为 [0 - 4] 五个状态，dp[i][j]表示第i天状态j所剩最大现金。

需要注意：dp[i][1]，表示的是第i天，买入股票的状态，并不是说一定要第i天买入股票，这是很多同学容易陷入的误区。

func maxProfit(prices []int) int {
    if len(prices) == 0 {
        return 0
    }
    dp := make([][]int, len(prices))
    for i := 0; i < len(prices); i++ {
        dp[i] = make([]int, 5)
    }
    dp[0][1] = -prices[0]
    dp[0][3] = -prices[0]
    for i := 1; i < len(prices); i++ {
        dp[i][1] = max(dp[i - 1][1], -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])
        dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i])
    }
    return dp[len(prices) - 1][4]
}