2023-01-20发表2023-02-02更新代码能力 / 总结5 分钟读完 (大约755个字)

动态规划-股票交易问题

类型特点

股票买卖类问题的「状态」有三个，第一个是天数，第二个是允许交易的最大次数，第三个是当前的持有状态（即之前说的 rest 的状态，我们不妨用 1 表示持有，0 表示没有持有）。然后我们用一个三维数组就可以装下这几种状态的全部组合：

dp[i][k][0 or 1]
0 <= i <= n - 1, 1 <= k <= K
n 为天数，大 K 为交易数的上限，0 和 1 代表是否持有股票。
此问题共 n × K × 2 种状态，全部穷举就能搞定。

for 0 <= i < n:
    for 1 <= k <= K:
        for s in {0, 1}:
            dp[i][k][s] = max(buy, sell, rest)

对应的两个状态分别为：

dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
              max( 今天选择 rest,        今天选择 sell       )
  
  
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
              max( 今天选择 rest,         今天选择 buy         )

具体题目

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

相关企业

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
     随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

解法

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # dp[m][k][1/0] 在第 m 天，最多交易 k 笔，是否持有股票的最多收益

        m = len(prices)
        dp = [[[0,0] for _ in range(3)] for _ in range(m+1)]
        
        # 第0天的时候，不应当持有股票
        for i in range(3):
            dp[0][i][1] = -math.inf

        # 交易 0 次的时候，也不应当持有股票
        for i in range(m+1):
            dp[i][0][1] = -math.inf

        for i in range(1,m+1):
            for j in range(1,3):
                dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i-1])
                dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i-1])
        return dp[m][2][0]