1 买股票最好时机（一）

class Solution:
    def maxProfit(self , prices: List[int]) -> int:
        dp = [[0]*2 for _ in range(len(prices) )]

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

        for i in range(1, len(prices)):
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i]) # 当天不持股
            dp[i][1] = max(dp[i-1][1], -prices[i]) # 当天持股

        return dp[-1][0]

解题思路

1. 令dp[][0]为当前不持股的最大收益，dp[][1]为当前持股的最大收益。
2. 初始状态：dp[0][0]为第一天不买入，dp[0][1]为第一天买入。
3. 状态转移方程：

• 第i天不持股的最大收益，有两种情况：第一种情况是之前卖出去了，但是今天没有买；第二种情况是今天卖出去了。取这两者的最大值，即dp[i][0]=max(dp[i-1][0], dp[i-1][1]+prices[i])。
• 第i天持股的最大收益，有两种情况：第一种情况是之前买进来了；第二种情况是今天买进来了。取这两者的最大值，即dp[i][1] = max(dp[i-1][1], -prices[i])。

复杂度

• 时间复杂度和空间复杂度都为O（N）。

2 买股票最好的时机（二）

class Solution:
    def maxProfit(self , prices: List[int]) -> int:
        dp = [[0]*2 for _ in range(len(prices))]

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

        for i in range(1, len(prices)):
            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])

        return dp[-1][0]

3 买股票最好的时机（三）

class Solution:
    def maxProfit(self , prices: List[int]) -> int:

        dp = [[-10000]*5 for _ in range(len(prices))]

        dp[0][0] = 0 # 第一天没买
        dp[0][1] = -prices[0] # 第一天买了

        for i in range(1, len(prices)):
            dp[i][0] = dp[i-1][0]
            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]) # 买入第二次
            dp[i][4] = max(dp[i-1][4], dp[i-1][3]+prices[i]) # 卖出第二次

        return max(dp[-1][2], max(0, dp[-1][-1]))