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

    技术2022-07-11  125

    题目

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

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

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

    示例 1:

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

    示例 2:

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

    解题思路

    和买卖股票的最佳时机 III思路基本一致 可以对k进一步优化:对每次股票的最多交易次数应该是len(prices) / 2,比如有5天的价格,那么最频繁的交易就是买入、卖出、买入、卖出共4次。当给的k值大于这个阈值时,实际上就退化为买卖股票的最佳时机 II(无限次交易)了。

    赋初值时同样,因为i和k可能会变负数,所以对i = 0和k = 0的情况分别赋初值即可

    代码

    class Solution: def max_profit_infty(self, prices: list) -> int: dp_0, dp_1 = 0, -prices[0] for each_price in prices[1:]: dp_0, dp_1 = max(dp_0, dp_1 + each_price), max(dp_1, dp_0 - each_price) return dp_0 def maxProfit(self, k: int, prices: List[int]) -> int: if len(prices) < 2 or k == 0: return 0 n = len(prices) if k >= (n >> 1): return self.max_profit_infty(prices) int_min = -100000 dp = [[[0] * (k + 1) for _ in range(2)] for _ in range(n)] # init # i = 0 dp[0][0][0] = 0 dp[0][0][1] = int_min dp[0][1][0] = int_min dp[0][1][1] = -prices[0] for j in range(2, k + 1): dp[0][0][j] = int_min dp[0][1][j] = int_min # j = 0 for i in range(1, n): dp[i][0][0] = 0 dp[i][1][0] = int_min # dp for i in range(1, n): for j in range(1, k + 1): dp[i][0][j] = max(dp[i - 1][0][j], dp[i - 1][1][j] + prices[i]) dp[i][1][j] = max(dp[i - 1][1][j], dp[i - 1][0][j - 1] - prices[i]) return max(dp[-1][0])
    Processed: 0.015, SQL: 10