买卖股票的最佳时机IV

Leetcode Link: 188. 买卖股票的最佳时机 IV - 力扣（LeetCode）

题目

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

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

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

解法一

从暴力递归到动态规划

思路和买卖股票的最佳时机III 几乎一样，是其的推广。

暴力递归

简单，把III的代码中抄过来就行

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
 
        @functools.lru_cache()
        def process(state, n, i):
	        # state-持有状态 n-卖出次数 i-第i天
	        # 返回最大利润
            if n == 0 or i == len(prices):
                return 0
            
            if state == 0:
                p1 = process(0, n, i+1)
                p2 = process(1, n, i+1) - prices[i]
            else:
                p1 = process(1, n, i+1)
                p2 = process(0, n-1, i+1) + prices[i]
            return max(p1, p2)
        
        return process(0, k, 0)

这个会超时，即使有 lru_cache()

动态规划

没什么好说的，干就完了。

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        # [state: (0,1), n:k, i:len(prices)]
        dp = [[[0 for _ in range(len(prices)+1)] for _ in range(k+1)] for _ in range(2)]
 
        # 需要将最后一层初始化
        # 不用写，本来就是0
 
        for i in range(len(prices)-1, -1, -1): # i == len(prices) 是 base case
            for n in range(1, k+1):  # n = 0 是base case
                dp[0][n][i] = max(dp[0][n][i+1], dp[1][n][i+1]-prices[i])
                dp[1][n][i] = max(dp[1][n][i+1], dp[0][n-1][i+1]+prices[i])
        return dp[0][k][0]

启发和联系