day54 动态规划part11 代码随想录算法训练营 123. 买卖股票的最佳时机 III

题目：123. 买卖股票的最佳时机 III

我的感悟：

• 困难像弹簧，你强他就弱，你弱它就强！

理解难点：

• 5个状态，

听课笔记：

我的代码：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices)==1:
            return 0
        # 5种状态
        # dp[i][0] 什么都不操作
        # dp[i][1] 第i天第1次已经买入
        # dp[i][2] 第i天第1次已经卖出
        # dp[i][3] 第i天第2次已经买入
        # dp[i][4] 第i天第2次已经卖出
        dp = [[0] * 5 for _ in range(len(prices))]
        # 初始化
        dp[0][1] = 0-prices[0]  # 买入，手里的钱是负数
        dp[0][3] = 0-prices[0]  # 同理
        for i in range(1,len(prices)):
            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 dp[-1][4]

通过截图：

老师代码：

差不多

扩展写法：

资料：

这道题一下子就难度上来了，关键在于至多买卖两次，这意味着可以买卖一次，可以买卖两次，也可以不买卖。

视频讲解：https://www.bilibili.com/video/BV1WG411K7AR

https://programmercarl.com/0123.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BAIII.html