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

发表于 分类于
这是文章开头，显示在主页面，详情请点击此处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
description: "这是文章开头，显示在主页面，详情请点击此处。"
categories: 
- "leecode刷题复习"
tags:
- "动态规划"
- "股票问题"class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 定义 五个状态 d[i][0] = 第i天 不操作
        # d[i][1] = 第i天第一次持有；
        # d[i][2] = 第i天第一次不持有；
        # d[i][3] = 第i天第二次持有；
        # d[i][4] = 第i天第二次不持有；
        # 初始化 ；同一天多次买卖，这样取理解；
        d = [[0,0,0,0,0] for _ in range(len(prices))]
        d[0][0] = 0
        d[0][1] = -prices[0]
        d[0][2] = 0
        d[0][3] = -prices[0]
        d[0][4] = 0 
        for i in range(1,len(prices)):
            d[i][0] = d[i-1][0]
            d[i][1] = max(d[i-1][1],d[i-1][0]-prices[i])
            d[i][2] = max(d[i-1][2],d[i-1][1]+prices[i])
            d[i][3] = max(d[i-1][3],d[i-1][2]-prices[i])
            d[i][4] = max(d[i-1][4],d[i-1][3]+prices[i])
            # print(d)
        return max(d[len(prices)-1][0],d[len(prices)-1][1],d[len(prices)-1][2],d[len(prices)-1][3],d[len(prices)-1][4])