借楼。
@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

按照老师的办法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;
    }

看了其他人的留言，@Miletos同学的第一个问题，白板上方程2）应该是对的，方程1）中后一个dp应该由 dp[i - 1][1][k - 1] + a[i]修改为dp[i - 1][0][k] +a[i] （即将k-1修改为k）
我理解的交易次数是，买入时增加交易次数，卖出时交易次数不变。
方程1) dp[i][0][k] = MAX{ dp[i - 1][0][k], dp[i - 1][0][k] +a[i]};MAX的后一个式子即是前面交易了k次，持股，当前第i天完成第k次交易的卖出操作。
我修改过的状态转移方程应该跟@farFlight同学的留言一致

写了一个单数组的JS实现来，空间优化为O(n)。思路是观察到DP状态转移的两个函数并不会覆盖到需要使用的前一天的值，所以单个数组就足够应付了。

```
var maxProfit = function(k, prices) {
  if (k <= 0 || !prices || prices.length <= 1) {
    return 0;
  }
  
  const MIN = Number.NEGATIVE_INFINITY;
  // mp[0...k -> # of transaction][0 -> no stock, 1 -> has stock]
  const mp = [
    [0, MIN],
    [0, -prices[0]],
  ];
  
  for (let i = 1; i < prices.length; i++) {
    
    const maxK = Math.min(k, Math.floor(i / 2) + 1);
    
    for (let j = 1; j <= maxK; j++) {
      if (j >= mp.length) {
        // new transaction for the day, must be buy
        mp[j] = [MIN, mp[j - 1][0] - prices[i]];
        // each day can only add one more transaction, so we are done
        break;
      }
      
     // This DP function won't accidentally overwrite needed values from
     // previous day, so a single array is enough
      mp[j][0] = Math.max(mp[j][0], mp[j][1] + prices[i]);
      mp[j][1] = Math.max(mp[j][1], mp[j - 1][0] - prices[i]);
    }
  }
  
  let max = MIN;
  
  for (let j = 0; j < mp.length; j++) {
    if (mp[j][0] > max) {
      max = mp[j][0];
    }
  }
  
  return max;
};
```

Python 代码 最多交易k次的情况 终于跑通了额。。
class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)
        if n == 0:
            return 0
        
        if k >= n//2:
            res = 0
            for i in range(n-1):
                if prices[i] < prices[i+1]:
                    res += prices[i+1] - prices[i]
        else:
            res = -float('inf')
            dp = [[[0 for i in range(2)] for j in range(k+1)] for m in range(n)]

            # 第二维 当前交易次数
            # 第三维 当前是否持仓
            for i in range(k+1):
                dp[0][i][0],dp[0][i][1] = 0,-prices[0]

 
            for i in range(1,n):
                for j in range(0,k+1):
                    if j == 0:
                        dp[i][j][0] = dp[i-1][j][0]
                    else:
                        dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j-1][1]+prices[i])
                    dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j][0]-prices[i])
                
            for i in range(k+1):
                res = max(res, dp[n-1][i][0])
        
        return res

这是按照老师的方法实现的python代码，同时参考楼上@以安的 JAVA 实现
class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        if not prices:
            return 0
        # the problem will become a greedy problem if k is larger than the half length
        if k > len(prices) / 2:
            res = 0
            for i in range(1, len(prices)):
                if prices[i] > prices[i-1]:
                    res += prices[i] - prices[i-1]
            return res
        
        dp = [[[float("-inf")] * 2 for i in range(k+1)] for i in range(len(prices))]
        # init
        for kk in range(k+1):
            dp[0][kk][0] = 0
            dp[0][kk][1] = - prices[0]
            
        for i in range(1, len(prices)):
            for kk in range(k+1):
                # need to handle the special case when kk == 0
                dp[i][kk][0] = max(dp[i-1][kk][0], dp[i-1][kk-1][1] + prices[i]) if kk > 0 else dp[i-1][kk][0]
                dp[i][kk][1] = max(dp[i-1][kk][0] - prices[i], dp[i-1][kk][1])
        return max([dp[-1][kk][0] for kk in range(k+1)])