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

题目

给你一个整数数组 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

解答

思路：记忆化搜索

由于需要统计交易次数，因此在递归函数中增加一个参数 j 表示当前交易次数：

• dfs(i, j, 0) 表示到第 $i$ 天结束时完成 至多 $j$ 笔交易，且未持有股票的最大利润
• dfs(i, j, 1) 表示到第 $i$ 天结束时完成 至多 $j$ 笔交易，且持有股票的最大利润
• 买入卖出算一笔交易，因此交易次数在买入的时候就 -1

转移方程：

$$\begin{array}{rl}& \text{dfs}(i,j,0)=max(\text{dfs}(i-1,j,0),\text{dfs}(i-1,j,1)+\text{prices}[i])\\ & \text{dfs}(i,j,1)=max(\text{dfs}(i-1,j,1),\text{dfs}(i-1,j-1,0)-\text{prices}[i])\end{array}$$

由于这个是一个三维 DP，因此递归边界需要慎重思考：

• dfs(, -1, ) = -inf 任何情况下，交易次数都不能 < 0，直接让它不可能成为答案
• dfs(-1, j, 0) = 0 第 0 天开始时，没有持有股票，利润为 0
• dfs(-1, j, 1) = -inf 第 0 天开始时，持有股票，这种情况不可能发生，利润为 0
• 总之就是不可能的情况设置为 -inf，让它不可能成为答案

递归入口：

$$max(\text{dfs}(n-1,k,0),\text{dfs}(n-1,k,1))=\text{dfs}(n-1,k,0)$$

由于多了一维 $k$，因此：

• 时间复杂度为 $O(2nk)$
• 空间复杂度为 $O(2nk)$

代码

Python 代码

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)

        @cache
        def dfs(i, j, hold):
            if j < 0:
                return -inf
            
            if i < 0:
                return -inf if hold else 0
            
            if hold:
                return max(dfs(i - 1, j, True), dfs(i - 1, j - 1, False) - prices[i])
            
            return max(dfs(i - 1, j, False), dfs(i - 1, j, True) + prices[i])
        
        return dfs(n - 1, k, False)

说第 $i$ 天购买了股票太含糊了，说第 $i$ 天 结束时持有股票 最精准。

注意，写成下面这种情况也是对的（看作卖出是算完成了一次交易），这是因为就算已经完成了 $k$ 次交易的同时买入了股票并且尚未卖出，由于此时一定是亏的，所以对答案没有影响。

if hold:
    return max(dfs(i - 1, j, True), dfs(i - 1, j, False) - prices[i])

return max(dfs(i - 1, j, False), dfs(i - 1, j - 1, True) + prices[i])

思路：递推

翻译成递推公式：

$$\begin{array}{rl}& f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]+\text{prices}[i])\\ & f[i][j][1]=max(f[i-1][j][1],f[i-1][j-1][0]-\text{prices}[i])\end{array}$$

防止负数下标，由于 i 直接和 prices 相关，因此对 f 全部 +1，而 j 独立，因此我们只需要让 j >= 1 即可：

$$\begin{array}{rl}& f[i+1][j][0]=max(f[i][j][0],f[i][j][1]+\text{prices}[i])\\ & f[i+1][j][1]=max(f[i][j][1],f[i][j-1][0]-\text{prices}[i])\end{array}$$

以及：

• 递推入口：f[][0][] = -inf, f[0][j][0] = 0, f[0][j][1] = -inf, j >= 1
• 递推答案：f[n][k + 1][0]

代码

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)

        f = [[[-inf] * 2 for _ in range(k + 2)] for _ in range(n + 1)]
        for j in range(1, k + 2):
            f[0][j][0] = 0
        
        for i, p in enumerate(prices):
            for j in range(1, k + 2):
                f[i + 1][j][0] = max(f[i][j][0], f[i][j][1] + p)
                f[i + 1][j][1] = max(f[i][j][1], f[i][j - 1][0] - p)

        return f[n][k + 1][0]

思路：空间优化

由于：

• f[i + 1][j][0] 只与 f[i][j][0], f[i][j][1] 有关
• f[i + 1][j][1] 只与 f[i][j][1], f[i][j - 1][0] 有关

因此显然可以去掉第一维。

• f[j][0] = max(f[j][0], f[j][1] + p)，f[j][0] 修改不会影响 f[j][1]
• f[j][1] = max(f[j][1], f[j - 1][0] - p) 似乎应该从右往左遍历？

代码

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)

        f = [[-inf] * 2 for _ in range(k + 2)]
        for j in range(1, k + 2):
            f[j][0] = 0
        
        for p in prices:
            for j in range(1, k + 2):
                f[j][0] = max(f[j][0], f[j][1] + p)
                f[j][1] = max(f[j][1], f[j - 1][0] - p)

        return f[k + 1][0]

其实正反遍历都能对：

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)

        f = [[-inf] * 2 for _ in range(k + 2)]
        for j in range(1, k + 2):
            f[j][0] = 0
        
        for p in prices:
            for j in range(k + 1, 0, -1):
                f[j][0] = max(f[j][0], f[j][1] + p)
                f[j][1] = max(f[j][1], f[j - 1][0] - p)

        return f[k + 1][0]

从左往右遍历等价于：

$$\begin{array}{rl}& \text{dfs}(i,j,0)=max(\text{dfs}(i-1,j,0),\text{dfs}(i,j,1)+\text{prices}[i])\\ & \text{dfs}(i,j,1)=max(\text{dfs}(i-1,j,1),\text{dfs}(i,j-1,0)-\text{prices}[i])\end{array}$$

TODO

这个递归方程也是对的，为什么呢？

思路：恰好与至少

区别主要在边界条件上：

• 恰好交易 $k$ 次：f[0][1][0] = 0, f[0][j][0] = -inf, j != 1，其他初始化条件不变
• 至少交易 $k$ 次：
  • f[i][0][]：没有交易次数限制下，第 $i$ 天结束时最大利润，等同于 122 题
  • 因此初始条件也需要状态转移计算出来：
  • f[i + 1][0][0] = max(f[i][0][0], f[i][0][1] + p)
  • f[i + 1][0][1] = max(f[i][0][1], f[i][0][0] - p)
  • f[0][0][0] = 0，其余初始条件不变

代码

恰好交易 $k$ 次

记忆化搜索：

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        # 记忆化搜索
        @cache
        def dfs(i: int, j: int, hold: bool) -> int:
            if j < 0:
                return -inf
        
            if i < 0:
                return -inf if hold or j > 0 else 0 # 修改这里
        
            if hold:
                return max(dfs(i - 1, j, True), dfs(i - 1, j - 1, False) - prices[i])
            
            return max(dfs(i - 1, j, False), dfs(i - 1, j, True) + prices[i])
        
        return dfs(n - 1, k, False)

改写递推：

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        # 递推
        n = len(prices)

        f = [[[-inf] * 2 for _ in range(k + 2)] for _ in range(n + 1)]
        f[0][1][0] = 0  # 只需改这里
        
        for i, p in enumerate(prices):
            for j in range(1, k + 2):
                f[i + 1][j][0] = max(f[i][j][0], f[i][j][1] + p)
                f[i + 1][j][1] = max(f[i][j][1], f[i][j - 1][0] - p)
        
        return f[-1][-1][0]

至少交易 $k$ 次

记忆化搜索：

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        # 记忆化搜索
        @cache
        def dfs(i: int, j: int, hold: bool) -> int:
            if i < 0:
                return -inf if hold or j > 0 else 0 # 把 f[i][j < 0][0] 当作 f[i][0][0] 来使用了
            
            if hold:
                return max(dfs(i - 1, j, True), dfs(i - 1, j - 1, False) - prices[i])
            
            return max(dfs(i - 1, j, False), dfs(i - 1, j, True) + prices[i])
        
        return dfs(n - 1, k, False)

改写递推：

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        # 递推
        n = len(prices)
        
        f = [[[-inf] * 2 for _ in range(k + 1)] for _ in range(n + 1)]
        f[0][0][0] = 0
        
        for i, p in enumerate(prices):
            f[i + 1][0][0] = max(f[i][0][0], f[i][0][1] + p)
            f[i + 1][0][1] = max(f[i][0][1], f[i][0][0] - p)  # 无限次
        
            for j in range(1, k + 1):
                f[i + 1][j][0] = max(f[i][j][0], f[i][j][1] + p)
                f[i + 1][j][1] = max(f[i][j][1], f[i][j - 1][0] - p)
        
        return f[-1][-1][0]