美文网首页
LeetCode-123-买卖股票的最佳时机 III

LeetCode-123-买卖股票的最佳时机 III

作者: 阿凯被注册了 | 来源:发表于2020-10-03 10:16 被阅读0次
    image.png

    解题思路1 (动态规划):

    1. dp_0[i][k]: 表示 第i天交易了k次时空仓的累计最大利润
      dp_1[i][k]: 表示 第i天交易了k次时持仓的累计最大利润

    2. 初始状态:第i天空仓且之前没交易过,由初始状态转移过来,即昨天也空仓,dp_0[i][0] = dp_0[i-1][0]

    3. 第一次买入:第i天持仓且之前没交易过,由两个状态转移过来,即昨天空仓,今天买入,或者昨天持仓今天继续持仓:
      dp_1[i][0] = max(dp_1[i-1][0], dp_0[i-1][0]-prices[i])

    4. 第一次卖出:第i天空仓且之前交易过,由两个状态转移过来,即昨天空仓今天继续空仓,或者昨天持仓今天卖出,因为卖出才算完成交易昨天持仓今天卖出,昨天持仓状态的k=0:
      dp_0[i][1] = max(dp_0[i-1][1], dp_1[i-1][0]+prices[i])

    5. 第二次买入 第i天持仓且之前交易过一轮,有两个状态转移过来,即昨天持仓今天继续持仓,或者昨天空仓今天买入,
      dp_1[i][1] = max(dp_1[i-1][1], dp_0[i-1][1]-prices[i])

    6. 第二次卖出 即第i天空仓且k=2,由一个状态转移过来,即昨天空仓,今天继续空仓,或者昨天持仓今天卖出,
      dp_0[i][2] = max(dp_0[i-1][2], dp_1[i-1][1]+prices[i])

    python3代码如下:

    class Solution:
        def maxProfit(self, prices: List[int]) -> int:
            len1 = len(prices)
            max_k = 2
            dp_0 = [[0 for _ in range(max_k+1)] for _ in range(len1)]
            dp_1 = [[0 for _ in range(max_k+1)] for _ in range(len1)]
    
            dp_0[0][0] = 0
            dp_1[0][0] = -prices[0]
            dp_0[0][1] = 0 # 第0天空仓且已经交易了1次,不存在该情况
            dp_1[0][1] = -prices[0] # 第0天持仓,且交易了一次,即买入,
            dp_0[0][2] = 0 # 第0天空仓且已经交易了2次, 不存在该情况
            # dp_1[0][2] = -prices[0] # 第0天持仓,且交易了一次,不存在该情况
    
            for i in range(1, len(prices)):
                # 初始
                dp_0[i][0] = dp_0[i-1][0]
    
                # 第一次买入、第一次卖出
                dp_1[i][0] = max(dp_1[i-1][0], dp_0[i-1][0]-prices[i])
                dp_0[i][1] = max(dp_0[i-1][1], dp_1[i-1][0]+prices[i])
    
                # 第二次买入、第二次卖出
                dp_1[i][1] = max(dp_1[i-1][1], dp_0[i-1][1]-prices[i])
                dp_0[i][2] = max(dp_0[i-1][2], dp_1[i-1][1]+prices[i])
    
            return max(dp_0[-1])
    

    相关文章

      网友评论

          本文标题:LeetCode-123-买卖股票的最佳时机 III

          本文链接:https://www.haomeiwen.com/subject/rjmuuktx.html