188. 买卖股票的最佳时机 IV
困难
867
相关企业
给定一个整数数组 prices ，它的第 **i 个元素 prices[i] 是一支给定的股票在第 i **天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 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 。
```py ‘’’ 这道题是股票类问题的最泛化题目，如果搞懂这道题其他股票类题目就容易理解了 首先，需要知道股票收益和什么有关？ 容易想到和前一天是否买入卖出 最大的交易数 有关，根据这些状态，我们定义 f[i][j][k] k=0/1 表示 第i天结束时，最多进行了j笔交易后，手上有/无股票的最大收益 转移方程如下
f[i][k][0]=max(f[i-1][k][0],f[i-1][k][1]+price[i]) 第i天手上有股票的收益 = 前一天手上有股票 或者 前一天手上没有股票，且最多进行了k-1笔收益，今天买入股票的收益 f[i][k][1]=max(f[i-1][k][1],f[i-1][k-1][0]-price[i]) ‘’’’
class Solution: def maxProfit(self, k: int, prices: List[int]) -> int: n = len(prices) # 不限制交易次数时的最大收益 def maxProfit_k_inf(prices): f=[[0,0]for i in range(n+1)] f[1][0]=0 f[1][1]=-prices[0] for i in range(2,n+1): f[i][0]=max(f[i-1][0],f[i-1][1]+prices[i-1]) f[i][1]=max(f[i-1][1],f[i-1][0]-prices[i-1]) return f[n][0] # 一笔交易需要两天，n天最多可以进行n//2笔交易，如果最多的天数k>n//2的话，就相当于可以有任意笔交易 if k > n / 2: return maxProfit_k_inf(prices) # f[i][j][k] 第i天结束时，最多进行了j笔交易，当前手上有/无股票的最大收益 f = [[[0] * 2 for _ in range(k+1)] for _ in range(n+1)] # 从第一天开始递推 for i in range(1,n+1): # prices下标从0开始，第一天对应prices[0] 第i天对应prices[i-1] p=prices[i-1] # 从最多进行1次交易开始递推 for j in range(1, k+1): # 如果是第一天 if i==1: f[i][j][0] = 0 f[i][j][1] = -p else: f[i][j][0] = max(f[i-1][j][0], f[i-1][j][1] + p) f[i][j][1] = max(f[i-1][j][1], f[i-1][j-1][0] - p) return f[n][k][0]