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

题目

给定一个数组，它的第 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 。

解答

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/solution/dong-tai-gui-hua-by-liweiwei1419-4/

• 边界条件判断

• 如果可以操作的机会很多，那么完全可以吃下每一次的利润

• 如果当天持有股票，那么说明前一天买了；

  如果没持有，说明前一天卖了

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        if not prices or len(prices) < 2 or k == 0:
            return 0
        size = len(prices)
        if k >= size//2:
            res = 0
            for i in range(1, size):
                if prices[i] > prices[i-1]:
                    res += prices[i]-prices[i-1]
            return res
        dp = [[[0, float('-inf')] for _ in range(k+1)] for _ in range(size+1)]
        for i in range(1, size+1):
            for j in range(1, k+1):
                dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0]-prices[i-1])
                dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1]+prices[i-1])
        return dp[size][k][0]

Runtime: 168 ms, faster than 13.31% of Python3 online submissions for Best Time to Buy and Sell Stock IV.

Memory Usage: 24.6 MB, less than 16.67% of Python3 online submissions for Best Time to Buy and Sell Stock IV.

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/discuss/54131/Well-explained-Python-DP-with-comments

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        if not prices or len(prices) < 2 or k == 0:
            return 0
        size = len(prices)
        if k >= size//2:
            res = 0
            for i in range(1, size):
                if prices[i] > prices[i-1]:
                    res += prices[i]-prices[i-1]
            return res
        profits = [0] * size
        for j in range(k):
            preprofit = 0
            for i in range(1, len(prices)):
                profit = prices[i]-prices[i-1]
                preprofit = max(preprofit+profit, profits[i])
                profits[i] = max(profits[i-1], preprofit)
        return profits[-1]

Runtime: 104 ms, faster than 77.38% of Python3 online submissions for Best Time to Buy and Sell Stock IV.

Memory Usage: 13.4 MB, less than 100.00% of Python3 online submissions for Best Time to Buy and Sell Stock IV.