问题描述LeetCode188. 买卖股票的最佳时机 IV给定一个数组它的第i个元素是一支给定的股票在第i天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成k笔交易。注意:你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。示例 1:输入:[2,4,1], k 2输出:2解释:在第 1 天 (股票价格 2) 的时候买入在第 2 天 (股票价格 4) 的时候卖出这笔交易所能获得利润 4-2 2 。示例 2:输入:[3,2,6,5,0,3], k 2输出:7解释:在第 2 天 (股票价格 2) 的时候买入在第 3 天 (股票价格 6) 的时候卖出, 这笔交易所能获得利润 6-2 4 。 随后在第 5 天 (股票价格 0) 的时候买入在第 6 天 (股票价格 3) 的时候卖出, 这笔交易所能获得利润 3-0 3 。问题分析这个问题应该是前一个问题的升级加强版了普通方法很容易超时在讨论区看看了大神的做法发现一种非常有趣但又比较难理解的方法总结起来基本是给出两种解释实现起来是一个代码只是对问题的角度不同而已。1、dp推导在每一笔交易中买--卖我们都会尽可能低价买入并尽可能以高价出售。在第二笔交易中将第一笔交易的利润与第二笔交易的成本相结合那么第二笔交易的利润就是两笔交易的总利润并以此类推。具体推导请参考大神fun4LeetCode在讨论的区的解答有点长耐心看。2、另一种解释是采用状态机进行说明具体可以参考MadDetective的程序。这种解释主要是把整个问题划分成几种状态并相互转换。图片来自MadDetective。其中hold表示股票持有状态手里有一只股票sold表示所有股票已经卖出手里没有股票。Python3实现class Solution: def maxProfit(self, k, prices): hold, sold [float(-inf)] * (k 1), [0] * (k 1) for price in prices: for j in range(1, k1): hold[j] max(hold[j], sold[j-1]-price) # hold-hold, sold-hold sold[j] max(sold[j], hold[j]price) # sold-sold, hold-sold return sold[k] if __name__ __main__: prices, k [7, 1, 5, 3, 6, 4], 4 solu Solution() print(solu.maxProfit(k, prices))hold[j]的物理含义是在遍历到当前价格时你正处于持有股票的状态且这次持有属于第 j 笔交易即已经买了第 j 只股票但还没卖。在买入之前你已经完成了 j-1 笔完整的买卖。sold[j]的物理含义是在遍历到当前价格时你正处于不持有股票的状态且已经完成了 j 笔完整的买卖交易。参考链接[1]:https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/discuss/108870/Most-consistent-ways-of-dealing-with-the-series-of-stock-problems[2]:https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/discuss/127020/Java-Solution-time-O(nk)-space-O(k)欢迎探讨。