按照老师的办法AC 188题可交易K次的java实现： public int maxProfit(int k, int[] prices) { if (prices == null || prices.length == 0) return 0; /** 当k大于等于数组长度一半时, 问题退化为贪心问题此时采用 买卖股票的最佳时机 II 的贪心方法解决可以大幅提升时间性能，如果不用这个贪心，有个testCase过不去，会报空间超 限 */ if(k >= prices.length / 2) return greedy(prices); int[][][] mp = new int[prices.length][2][k + 1]; for (int i = 0; i <= k; i++) { // 第 1 天买入 - 卖出循环 K 次之后不再买入，所以初始值为 0 mp[0][0][i] = 0; // 第 1 天买入 - 卖出循环 K 次之后又买入，所以初始值为 -prices[0] mp[0][1][i] = -prices[0]; } for (int i = 1; i < prices.length; i++) { for (int j = 0; j <= k; j++) { mp[i][0][j] = j != 0 ? Math.max(mp[i - 1][1][j - 1] + prices[i], mp[i - 1][0][j]) : mp[i - 1][0][j]; mp[i][1][j] = Math.max(mp[i - 1][0][j] - prices[i], mp[i - 1][1][j]); } } int max = Integer.MIN_VALUE; for (int i = 0; i <= k; i++) max = Math.max(max, mp[prices.length - 1][0][i]); return max; } private int greedy(int[] prices) { int max = 0; for(int i = 1; i < prices.length; ++i) { if(prices[i] > prices[i-1]) max += prices[i] - prices[i-1]; } return max; }

借楼。 @Mythxu 你对交易次数的理解为：买入时增加交易次数，卖出时交易次数不变，所以，在你的递推式中，0表示当前**持有**股票，1表示当前**不持有**股票。而我则与你相反，买入时不变，而卖出时视为完成一次交易，递推式中的0表示当前**不持有**股票，1表示当前**持有**股票。所以 我们对递推式的改动恰恰相反，总的来说，殊途同归。相同的是，白班上的递推方程确实是存在问题。[我的代码在LeetCode上AC了，确认无误。] @zixuan 我确实是注意到了，LeetCode 上的测试用例比较严格，当K远远大于len(prices)的时候，将会产生[Time Limit Exceed]。我认为你的方法应该可以解决该问题。我这里有另外一种更可靠，便捷的方法供参考：<Ref: http://www.cnblogs.com/grandyang/p/4295761.html> 当K远远大于pricesSize时，DP方法要维护的数组就会相应变的很大，这将导致其非常低效。从Best Time to Buy and Sell Stock II 可以看出，在最坏的情况下（递增序列），我们每次在第 i 天买入，第 i + 1 卖出，然后再在第 i + 1 天买入，第 i + 2天卖出。这里的无穷次交易，我们最多只需要进行N次（更准确的是N - 1 次）即可获得最大收益。因此，在最多进行K次交易的情况中，当K > N 时，可以认为进行无穷次交易，将算法由DP退化为Best Time to Buy and Sell Stock II 中简单的线性扫描+比较，这样时间复杂度由O(NK)降低为O(N)，空间复杂度由O(NK)将为O(1)。 代码[Accepted]见Github: https://github.com/fangxlmr/LeetCode/blob/master/188.%20Best%20Time%20to%20Buy%20and%20Sell%20Stock%20IV.c

本课程动态规划的转移方程讲的很好，老师，还是把K次代码贴岀来吧，被折腾几天了

为什么初始值要设置成负数最小值呢

1. 不知道是不是我一个人的问题：视频在播放到代码段的时候就卡住了，只能砍到交易两次的代码，看不到交易K次的代码，所以我无法验证问题2中白班上与代码是否匹配。 2. 我认为白板上的递推公式推导略微有些问题。 白板上的为： 1) dp[i][0][k] = MAX{ dp[i - 1][0][k], dp[i - 1][1][k - 1] + a[i]}; 2) dp[i][1][k] = MAX{ dp[i - 1][1][k], dp[i - 1][0][k - 1] - a[i]}; 我认为方程2)后一个dp应该由dp[i - 1][0][k - 1] - a[i]修改为dp[i - 1][0][k] - a[i]。评论中有人提到这一点了。 1) dp[i][0][k] = MAX{ dp[i - 1][0][k], dp[i - 1][1][k - 1] + a[i]}; 2) dp[i][1][k] = MAX{ dp[i - 1][1][k], dp[i - 1][0][k] - a[i]}; 其中，dp表示第i天，0->i天共交易了k次的最大获益。中间的0表示第i天不持有股票，1表示第i天持有股票； 3. 还需要注意的是边间条件的处理（代码细节）。 方程1) 中，当k = 0时，MAX中的第二个选项将会导致k - 1 < 0，数组越界，并且实际意义也是不对的，不可能在前面不发生交易的情况下持有1股股票。 这里应当有判断：k == 0时，该情况不可能发生，可将MAX中的第二项修改为INT_MIN （C语言表示）； 当k > 0时，保持dp[i - 1][1][k - 1] + a[i]不变。 4. 要说的是，我用C在LeetCode上测试，小规模数据时可以通过，大规模数据（K = 1000000, pricesSize非常大）时，总是出现莫名错误，还不知道是为什么。 代码见Github: https://github.com/fangxlmr/LeetCode/blob/master/188.%20Best%20Time%20to%20Buy%20and%20Sell%20Stock%20IV.c

这个状态转移方程有个疑问，卖买一次应该是一次交易，但是状态转移的时候，卖买都算了一次？

老师你这个状态方程有问题的。。这一套题我改了快三天了。。希望能更正 应该是这样的： f[i+1][k][1] = max(f[i][k][1], f[i][k-1][0]-p) f[i+1][k][0] = max(f[i][k][0], f[i][k][1]+p) 0的状态是第K次交易已经卖出，1是第K次交易刚刚买入，因此0的递推在1之后，并且需要用到1的数值

“买入并卖出”才能算一次完整的交易，所以光买入是不计入交易次数的，卖出的时候才能算一次交易。

老师好，两次交易这道题给的答案跑不过，我大概分析了下，是因为并非任意的 profit[i][j][k] 都是存在的，比如 profit[0][1][0] 就不存在。 我把初始状态都设置为 None ，后续运算中如果出现 None ，则运算结果也是 None ，最终跑过了。

188题按你写法不行，开辟三维空间的话，有一个testcase过不了，超过内存限制