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

链接：188.买卖股票的最佳时机IV
难度：Hard
标签：数组、动态规划
简介：设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。

题解 1 - typescript

• 编辑时间：2020-12-28
• 执行用时：120ms
• 内存消耗：44.6MB
• 编程语言：typescript
• 解法介绍：dp。

function maxProfit(k: number, prices: number[]): number {
    const len = prices.length;
    if (len === 0) return 0;
    k = Math.min(~~(len / 2), k);
    const buy = new Array(len).fill(0).map(() => new Array(k + 1).fill(0));
    const sell = new Array(len).fill(0).map(() => new Array(k + 1).fill(0));
    [buy[0][0], sell[0][0]] = [-prices[0], 0];
    for (let i = 1; i <= k; ++i) buy[0][i] = sell[0][i] = -Number.MAX_VALUE;
    for (let i = 1; i < len; ++i) {
      const price = prices[i];
      const prevBuy = buy[i - 1];
      const prevSell = sell[i - 1];
      buy[i][0] = Math.max(prevBuy[0], prevSell[0] - price);
      for (let j = 1; j <= k; ++j) {
        buy[i][j] = Math.max(prevBuy[j], prevSell[j] - price);
        sell[i][j] = Math.max(prevSell[j], prevBuy[j - 1] + price);
      }
    }
    return Math.max(...sell[len - 1]);
}

题解 2 - python

• 编辑时间：2023-10-04
• 执行用时：256ms
• 内存消耗：31.78MB
• 编程语言：python
• 解法介绍：dp[i][j][k]表示i天j笔手上有无。

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)
        # [i][j][k] i天j笔手上有无
        dp = [[[-inf for _ in range(2)] for _ in range(k + 1)] for _ in range(n + 1)]
        nums = [[-inf for _ in range(2)] for _ in range(k + 1)]
        res = dp[0][0][0] = dp[0][0][1] = nums[0][0] = 0
        for i in range(0, n):
            dp[i][0][0] = 0
            dp[i][0][1] = -prices[i]
            for j in range(1, k + 1):
                dp[i][j][0] = nums[j - 1][1] + prices[i]
                dp[i][j][1] = nums[j][0] - prices[i]
                res = max(res, dp[i][j][0])
            for j in range(0, k + 1):
                nums[j][0] = max(nums[j][0], dp[i][j][0])
                nums[j][1] = max(nums[j][1], dp[i][j][1])
        return res