买卖股票的最佳时机 IV

标签: 数组 动态规划

难度: Hard

给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。

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

示例 1：

输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

示例 2：

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

提示：

  • 1 <= k <= 100
  • 1 <= prices.length <= 1000
  • 0 <= prices[i] <= 1000

Submission

运行时间: 160 ms

内存: 24.5 MB

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)
        dp = dp = [ [[0, 1] for _ in range(k+1)]  for _ in range(n+1)]
        for i in range(1, n+1):
            for k in range(1, k+1):
                # base case
                if i == 1:
                    dp[i-1][k][0] = 0
                    dp[i-1][k][1] = float('-inf')
                dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1]+prices[i-1])
                dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0]-prices[i-1])
        return dp[-1][-1][0]

Explain

这个题解使用动态规划来解决问题。定义状态 dp[i][k][0] 表示第i天结束后最多进行k次交易且当前没有持有股票的最大利润，dp[i][k][1] 表示第i天结束后最多进行k次交易且当前持有股票的最大利润。然后基于当前是否持有股票、是否发生交易来进行状态转移。最后返回 dp[-1][-1][0] 即最后一天结束后最多进行 k 次交易且没有持有股票的最大利润。

时间复杂度: O(n*k)

空间复杂度: O(n*k)

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)
        # 定义状态数组，大小为 (n+1) * (k+1) * 2
        dp = [ [[0, 1] for _ in range(k+1)]  for _ in range(n+1)]
        
        for i in range(1, n+1):
            for k in range(1, k+1):
                # base case 处理
                if i == 1:
                    dp[i-1][k][0] = 0
                    dp[i-1][k][1] = float('-inf')
                    
                # 第 i 天未持有股票，可能保持前一天的状态，或者前一天持有股票今天卖出
                dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1]+prices[i-1])
                
                # 第 i 天持有股票，可能保持前一天的状态，或者前一天未持有股票今天买入（消耗了一次交易次数）
                dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0]-prices[i-1])
                
        # 返回最后一天结束后最多进行 k 次交易且没有持有股票的最大利润
        return dp[-1][-1][0]

Explore

在动态规划的数组定义中，需要三个维度来完整描述问题的状态。第一个维度i代表了天数，用于记录在第i天结束时的状态；第二个维度k代表了允许的最大交易次数，用于跟踪进行到当前的交易次数；第三个维度是二进制，用于表示当前是否持有股票（0表示未持有，1表示持有）。这样的三维表示可以帮助我们存储和更新每一天结束时，在不同交易次数和持有状态下的最大利润。

在初始化状态时，将 dp[i-1][k][1] 设为负无穷大是为了表示在还没有开始交易之前的不可能状态。因为在第一天之前不可能持有股票，所以设置为负无穷大可以防止这种状态被错误地计算入最优解。此外，这种设置也有利于在动态规划过程中正确处理买入股票的逻辑，确保只有在合适的条件下（即存在足够的交易次数和资金）才会考虑买入操作。

在状态转移时，dp[i][k][0] 的更新公式为 `max(dp[i-1][k][0], dp[i-1][k][1] + prices[i-1])`，这表示当前不持有股票的最大利润可以从两个状态转移而来：维持前一天不持有股票的状态，或者是前一天持有股票并在今天卖出。dp[i][k][1] 的更新公式为 `max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i-1])`，这表示当前持有股票的最大利润可以从两个状态转移而来：维持前一天持有股票的状态，或者是前一天不持有股票并在今天买入（这会消耗一次交易机会）。这两个公式共同确保了在每一天结束时，无论持有状态如何，都能计算出最大的可能利润。

如果第一天就进行买入操作，这在动态规划表中通过特定的初始化来反映。具体来说，第一天买入股票的情况会在初始化时设置 `dp[1][1][1] = -prices[0]`，表示在第一天结束时，进行了一次交易，并且持有股票，花费了等于第一天股票价格的金额。这种初始化确保了算法能够考虑从第一天开始就进行交易的可能性。