【代码随想录算法训练营】第50天 | 第九章 动态规划（十一）+ 复习第20天 第六章 二叉树（六）

主要内容

股票问题

动态规划题目

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

思路分析

1、每一天有5种状态：
状态0：无操作
状态1：第一次持有股票状态
状态2：第一次卖出股票状态
状态3：第二次持有股票状态
状态4：第二次卖出股票状态

2、递推公式
o第i天延续之前的无操作状态：
dp[i][0] = dp[i-1][0]

①第i天是第一次持有股票状态：
第i天第一次买入：dp[i][1] = dp[i-1][0]-prices[i]
第i天延续之前的买入状态：dp[i][1] = dp[i-1][1]

②第i天是第一次卖出股票状态：
第i天第一次卖出：dp[i][2] = dp[i-1][1]+prices[i]
第i天延续了之前的卖出状态： dp[i][2] = dp[i-1][2]

③第i天是第二次买入股票状态：
第i天第二次买入：di[i][3] = dp[i-1][2] - prices[i]
第i天延续了之前的买入状态：dp[i][3] = dp[i-1][3]

④第i天是第二次卖出股票状态：
第i天第二次卖出：dp[i][4] = dp[i-1][3] + prices[i]
第i天延续了之前的卖出状态：dp[i][4] = dp[i-1][4]

3、初始化
无操作：dp[0][0] = 0
第一次买入：dp[0][1] = -prices[0]
第一次卖出：dp[0][2] = 0
第二次买入：dp[0][3] = -prices[0]
第二次卖出：dp[0][4] = 0

代码

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        dp = [[0] * 5 for _ in range(n)]
        dp[0][0] = 0
        dp[0][1] = -prices[0]
        dp[0][2] = 0
        dp[0][3] = -prices[0]
        dp[0][4] = 0
        for i in range(1, n):
            dp[i][0] = dp[i-1][0]
            dp[i][1] = max(dp[i-1][0]-prices[i], dp[i-1][1])
            dp[i][2] = max(dp[i-1][1]+prices[i], dp[i-1][2])
            dp[i][3] = max(dp[i-1][2]-prices[i], dp[i-1][3])
            dp[i][4] = max(dp[i-1][3]+prices[i], dp[i-1][4])
        return dp[n-1][4]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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

思路分析

j为奇数是买入，偶数是卖出
分析同上

代码

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

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