这道题其实就是122题的一个标准化形式，是leetcode的一个惯例由简入难。

1.题目

原题：

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

例子：

输入: [3,2,6,5,0,3], k = 2
输出: 7
解释: 在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

2.解析

这道题和只交易两次、甚至只交易一次是一样的只不过思路更复杂一些。
1）判断数组是不是空，或者数据是不是都是一样的，如果这样直接返回0。
2）判断交易次数，因为不能同时买卖所以理论的最大交易次数是m//2，如果k大于这个数其实就是122不限制购买了。
3）现在考虑k满足不能同时买卖要求的情况。
动态规划思路，需要dp数组，minp最小价格。dp这个是二维的，生成方法是交易次数和交易天数之间形成的二维数组，方法见代码。更新方法，今天的最佳收益就是昨天的最佳收益，和当前价格减最小价格的差值，注意这个只跟第k次交易的前一天数据有关。那么minp怎么更新，其实还是老思路，之前最小值和当前价格减去上次交易收益的较少者。
（2）其他方法
想到更好的就更新。

3.python代码

class Solution:
    def maxProfit(self, prices, k):
        if not prices or len(set(prices)) == 1:
            return 0
        m = len(prices)
        if k > m//2:
            res = 0
            minj = prices[0]
            for i in range(1, m):
                if prices[i] > minj:
                    res += prices[i] - minj
                    minj = prices[i]
                else:
                    minj = min(minj, prices[i])
            return res
        else:
            dp = [[0]*(k+1) for _ in range(m)]
            for j in range(1, k+1):
                minp = prices[0] - dp[j-1][0]
                for i in range(1, m):
                    dp[i][j] = max(dp[i-1][j], prices[i]-minp)
                    minp = min(prices[i]-dp[i-1][j-1], minp)
            return dp[-1][-1]