链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/description/
题目：
给你一个整数数组 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 。
思路：
动态规划 (DP) 问题（递归 + 记忆化）
1.状态定义
根据求解的目标状态来定义，比如这里我们要计算第 i 天最多 k 笔交易的情况下的最大利润（要涵盖住所有变量）。（这里想到另一个能用dp解决的例子，斐波那契数列，它的状态很好保存，就是第n项的值，直接一维数组DP[]。）这里有两个变量分别是交易数、天数，怎么办呢？可以使用二维数组保存。
给出我们的状态（定义数组）如下：
DP[k][i] # 第i天的最大利润2.得出状态转移方程（从第 i 天状态转向第 i+1 天）
状态转移方程如下：
DP[k][i] = max(DP[k][i-1], DP[k-1][i-1] + prices[i])
# 今天最大利润的状态是 DP[k][i]，有两种可能：
# 1)昨天状态DP[k][i-1]，今天啥也不干
# 2）昨天最大利润的状态是DP[k-1][i-1]，今天卖了一支股票，获得 prices[i]的利润问题是，第 i 天可以卖的前提是之前买过，这里是假设卖之前都买过一次，那么，怎么确定哪一天买进了一只股票呢？
我们得找出在第 i 天判断之前 i-1 天内哪一天买才能得到最大利润，于是得到下面的状态转移方程：
DP[k][i] = max(DP[k][i - 1], prices[i] + tmpMax)
tmpMax = max(tmpMax, DP[k-1][i-1] - prices[i])
# tepMax 表示手上持有股票的前提下，i-1 天的总收益最大值。如果利润没翻倍的话它应该是个负数，所以它初始值设置为-price[0]，表示第一天就买入并不做任何操作，所以它的利润就是第一天股价的负值，后面股价随便怎么波动，它不卖那利润就是那个负数不变
# 今天最大利润的状态是 DP[k][i]，有两种可能：
# 1）昨天就除天数外一模一样的状态DP[k][i-1]，今天啥也不干
# 2）昨天或者之前哪一天最大利润的状态是 DP[k-1][i-1]，然后今天卖了一支股票，获得 prices[i]的利润（其实，越复杂的动态规划问题无非就是多几个参数的数组定义和多几条状态转移方程）
题解：
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
if not prices or k == 0:
return 0
n = len(prices)
DP = [[0] * n for _ in range(k + 1)] # DP[k][i] 表示在进行 k 次交易且到第 i 天时的最大利润
for k in range(1, k + 1): # 进行 1 到 k 次交易的情况
tmpMax = -prices[0] # tmpMax 初始化为第一天的股票价格的相反数（负数），记录当前交易次数下的最大利润
for i in range(1, n): # 对股票价格列表中的每一天进行循环，从第二天开始（索引为 1）
DP[k][i] = max(DP[k][i - 1], prices[i] + tmpMax) # 不交易 or 卖出
tmpMax = max(tmpMax, DP[k - 1][i - 1] - prices[i]) # 不买 or 在当天买
return DP[k][n - 1] # 返回进行 k 次交易且到最后一天时的最大利润，即 DP[k][n - 1]参考：