代码随想录 Day - 50｜#123 买卖股票的最佳时机 III｜#188 买卖股票的最佳时机 IV

清单

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

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

1. 题目

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

2. 思路

1. dp数组含义: 最多完成两笔交易，共存在五种状态 1.不交易 2. 第一次买入 3. 第一次卖出 4. 第二次买入 5. 第二次卖出 dp[i][j] 为第i天所能获取的最大利润， i 代表天数 j代表交易状态
2. 递推公式:
   1. 若i天均不操作: dp[i][0] = dp[i-1][0]
   2. 若i天第一次买入: dp[i][1] = max(dp[i-1][1] #前一天已买入, dp[i-1][0] - prices[i]) # i 天买入
   3. 第i天第一次卖出: dp[i][2] = max(dp[i-1][2] #前一天已卖出, dp[i-1][1] + prices[i]) # i 天卖出
   4. 若i天第二次买入: dp[i][3] = max(dp[i-1][3] #前一天已买入, dp[i-1][2] - prices[i]) # i 天买入
   5. 第i天第二次卖出: dp[i][4] = max(dp[i-1][4] #前一天已卖出, dp[i-1][3] + prices[i]) # i 天卖出
3. 初始化: dp[0][1] = - prices[i] dp[0][3] = - prices[i]
4. 遍历顺序: 正向遍历

3. 代码实现

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

        dp[0][1] = - prices[0]
        dp[0][3] = - 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 dp[-1][4]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

LeetCode #188 买卖股票的最佳时机 IV

1. 题目

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

2. 思路

思路同上一题一样，共存在2k+1种状态 0为不操作，奇数为买入，偶数为卖出

3. 代码实现

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

        dp = [[0] * ( 2 * k + 1) for _ in range(len(prices))]

        for i in range(1, 2 * k, 2):
            dp[0][i] = - prices[0]
        
        for i in range(1, len(prices)):
            for j in range(0, 2*k - 1, 2):
                dp[i][j+1] = max(dp[i-1][j+1], dp[i-1][j] - prices[i])
                dp[i][j+2] = max(dp[i-1][j+2], dp[i-1][j+1] + prices[i])
        
        return dp[-1][2*k]
1
2
3
4
5
6
7
8
9
10
11
12
13
14