【DP】买卖股票的最佳时机III

题源
-之前都是数组存，然后转移状态，这次是直接四个变量，非常神奇

-在该问题中，定义了五种状态，分别是：未进行过任何操作、只进行过一次买操作、进行了一次买操作和一次卖操作（完成了一笔交易）、在完成了一笔交易的前提下进行了第二次买操作以及完成了全部两笔交易。

-然后，通过状态转移方程计算第i天结束后这五个状态的最大利润。对于每种状态，给出了相应的转移方程，例如对于buy1状态，它可以保持不变或者在未进行任何操作的前提下以prices[i]的价格买入股票。

-此外，还提到了一个边界条件，即无论是否允许在同一天买入并卖出，最终的答案都不会受到影响，因为这一操作带来的收益为零。

比较买卖股票时机II 和这道题在DP上的区别：

1. 状态定义：

「买卖股票的最佳时机 II」：在这个问题中，可以使用两个状态来定义动态规划，即持有股票的状态和不持有股票的状态。
「买卖股票的最佳时机 III」：这个问题需要考虑更多的情况，因此需要定义五个状态，分别表示未进行操作、只进行过一次买操作、进行了一次买操作和一次卖操作、在完成了一笔交易的前提下进行了第二次买操作，以及完成了全部两笔交易。

2. 转移方程：

「买卖股票的最佳时机 II」：在这个问题中，持有股票状态的转移方程是根据前一天不持有股票的状态和当天的股票价格计算得到的。不持有股票状态的转移方程是根据前一天持有股票的状态和当天的股票价格计算得到的。
「买卖股票的最佳时机 III」：在这个问题中，每个状态的转移方程涉及其他状态的计算。具体而言，buy1状态的转移方程需要考虑buy1'状态（第i-1天的状态），sell1状态的转移方程需要考虑buy1'和sell1'状态，buy2状态的转移方程需要考虑sell1'状态，sell2状态的转移方程需要考虑buy2'状态。
3. 限制条件：

「买卖股票的最佳时机 II」：在这个问题中，没有交易次数的限制，可以进行尽可能多的交易。
「买卖股票的最佳时机 III」：在这个问题中，最多完成两笔交易，因此需要考虑交易次数的限制。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        buy1 = buy2 = -prices[0]
        sell1 = sell2 = 0
        for i in range(1, n):
            buy1 = max(buy1, -prices[i])
            sell1 = max(sell1, buy1 + prices[i])
            buy2 = max(buy2, sell1 - prices[i])
            sell2 = max(sell2, buy2 + prices[i])
        return sell2

作者：力扣官方题解
链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/solutions/552695/mai-mai-gu-piao-de-zui-jia-shi-ji-iii-by-wrnt/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。