188. 买卖股票的最佳时机 IV
给定一个整数数组
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 。
提示：
0 <= k <= 100
0 <= prices.length <= 1000
0 <= prices[i] <= 1000
法1 动态规划
思路
同123. 买卖股票的最佳时机 III 类似。捋清楚状态。
题解
class Solution: def maxProfit(self, k: int, prices: List[int]) -> int: if len(prices) <= 1: return 0 dp = [[0] * (k*2+1) for _ in range(len(prices))] # 初始化 dp[0][i] 当i为奇数时为 0-prices[0] for i in range(2*k+1): if i % 2 == 1: dp[0][i] = 0 - prices[0] print(dp) # 开始状态转移 for i in range(1, len(prices)): for j in range(0, 2*k + 1): # 还没进行过股票买卖 if j == 0: dp[i][j] = dp[i-1][j] # 第 j // 2 + 1次持股 elif j % 2 == 1: dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]-prices[i]) # 进行过 j // 2股票买卖，当前不持股 elif j % 2 == 0: dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + prices[i]) print(dp) return dp[-1][-1]
是 123. 买卖股票的最佳时机 III 题目的扩展，123题只能买卖两次，本题可以买卖K次，所以，只需要将123题目的变量扩大2*k即可。逻辑完全一样
class Solution: def maxProfit(self, k: int, prices: List[int]) -> int: if len(prices) <= 1 : return 0 buy = [-prices[0]] * (k+1) sell = [0] * (k+1) for price in prices: for i in range(1, k+1, 1): buy[i] = max(buy[i], sell[i-1]-price) sell[i] = max(sell[i], buy[i]+price) return sell[-1]