188. 买卖股票的最佳时机 IV - 力扣（LeetCode）
class Solution:def maxProfit(self, k: int, prices: List[int]) -> int:if not prices or k == 0:return 0n = len(prices)if k >= n // 2: # 等价于无限交易return sum(max(prices[i+1] - prices[i], 0) for i in range(n-1))# dp[i][j]，j=0表示未交易，j=1表示第一次买入，j=2表示第一次卖出，j=3表示第二次买入...dp = [[0] * (2 * k + 1) for _ in range(n)]# 初始化for j in range(1, 2 * k, 2): # 奇数位初始化为负数，表示买入状态dp[0][j] = -prices[0]# 递推填表for i in range(1, n):for j in range(1, 2 * k + 1):if j % 2 == 1: # 处理买入状态dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] - prices[i])else: # 处理卖出状态dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + prices[i])return dp[n-1][2*k]
