精选留言(6)

• 
  james

  2019-02-25

  老师, 能不能把所有可能的组合输出来, 而不是仅仅输出一个3, 想了下代码好像比较麻烦

  作者回复: 需要用回溯的办法！

  

   1
• 
  Aliliin

  2019-12-03

  PHP 的两种解法
   public $min = PHP_INT_MAX;
  
      /**
       * dfs 解法
       */
      function coinChange1($coins, $amount)
      {
          if (empty($coins)) return -1;
          if ($amount == 0) return 0;
          sort($coins);
          if ($amount < $coins[0]) return -1;
          $sum = 0;
          $this->dfs($coins, $amount, $sum, count($coins) - 1);
          return $this->min === PHP_INT_MAX ? -1 : $this->min;
      }
  
      function dfs($coins, $amount, $sum, $index)
      {
          if ($index < 0 || ($sum + $amount / $coins[$index] >= $this->min)) return;
          if ($amount == 0) {
              $this->min = min($this->min, $sum);
              return;
          }
          for ($i = $index; $i >= 0; --$i) {
              if ($amount < $coins[$i]) continue;
              $this->dfs($coins, $amount - $coins[$i], $sum + 1, $i);
          }
      }
  
      /**
       * 动态规划
       */
      function coinChange($coins, $amount)
      {
          $dp = array_fill(1, $amount + 1, $amount + 1);
          $dp[0] = 0;
          for ($i = 1; $i <= $amount; $i++) {
  // for ($j = 0; $j < count($coins); $j++) {
  // if ($coins[$j] <= $i) {
  // $dp[$i] = min($dp[$i], $dp[$i - $coins[$j]] + 1);
  // }
  // }
              foreach ($coins as $coin) {
                  if ($coin <= $i) {
                      $dp[$i] = min($dp[$i], $dp[$i - $coin] + 1);
                  }
              }
          }
          return $dp[$amount] > $amount ? -1 : $dp[$amount];
      }

  展开

  

  
• 
  陈志恒

  2019-09-28

  1.复杂度O（x*n）
  2.dp的两种题型：序列“选择”最优问题 序列“排列”（可重复）最优

  

  
• 
  海鱼美味

  2019-06-03

  这个题目是要求出最长子序列的长度，所以二分查找法适用，如果要求出内容，是用动态规划。

  

  
• 
  克劳德

  2019-03-04

  当amount = 2147483647时，视频中的代码是有问题的，很遗憾LeetCode并没有这样的TestCase

  作者回复: 可以帮忙改进下代码。

   1

  
• 
  松果

  2019-02-07

  如果不是返回上升序列的size，第二种方式数组维护上升元素是有问题的吧

  

  