精选留言(25)

• 
  Miletos

  2018-12-01

  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

  展开

  

   13
• 
  yaya

  2018-11-25

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

  

   9
• 
  Miletos

  2018-12-05

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

  展开

  作者回复: 👍🏻👍🏻

   1

   6
• 
  以安

  2019-04-30

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

  展开

  作者回复: 帅

   1

   3
• 
  暴走大绵羊

  2019-04-07

  老师，交易两次的代码好像不对呢，过不去

  

   3
• 
  Eric

  2019-02-11

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

  

   3
• 
  farFlight

  2018-11-30

  老师你这个状态方程有问题的。。这一套题我改了快三天了。。希望能更正
  应该是这样的：
  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的数值

  

   3
• 
  雯雯

  2018-11-26

  希望能贴出交易两次的代码，似乎状态转移方程并不对

  

   3
• 
  ssala

  2019-05-26

  又听到一个名词，状态压缩。

  

   2
• 
  一二三四五

  2019-03-05

  哥哥还是麻烦把K次的代码贴一下吧 ，自己写的根本整不出来 想要的结果，搞得都没得信心了

  

   2
• 
  Mythxu

  2018-12-05

  看了其他人的留言，@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同学的留言一致
  
  
  

  展开

  

   2
• 
  jaux

  2019-09-19

  写了一个单数组的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;
  };
  ```

  展开

  

   1
• 
  张青天

  2019-07-31

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

  

   1
• 
  王者归来

  2019-04-11

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

  作者回复: 多谢肯定！ 现在没法补贴代码了，不过leetcode的讨论区里就有的。

  

   1
• 
  1011001

  2019-12-02

  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

  展开

  

  
• 
  关

  2019-11-08

  跪了
  

  

  
• 
  陈志恒

  2019-09-28

  技巧：有n个限制条件》n+1状态维度

  

  
• 
  Hc_Zzz

  2019-07-05

  这是按照老师的方法实现的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)])

  展开

  

  
• 
  丝雨

  2019-05-30

  当可以同时持有n 股的话，我觉得可以先计算出最多可持有一股时最大的收益，然后乘以n 就行

  

  
• 
  ssala

  2019-05-27

  找出问题的所有正交维来定义问题模型，dp的关键。

  

  