HoneyHoney

给指定的硬币类型，用最少的硬币个数，找出指定的amount。比如，现在有[2, 5, 10, 20, 50]这几种硬币，找出21块钱出来。

这个其实是算法导论里面动态规划。无意间，发现还有其他的实现方法。记录下来。

首先是动态规划。原来是，21块钱，可以拆分成19+2， 16+5， 11+10， 1+20。19又可以继续拆分成17+2, 14+5, 9+10。以此类推下去。里面有个技术点就是，还可以用block去定义Hash，厉害了。代码如下：

 def change(coins, amount, results = [])
    return [] if amount == 0

    coins.sort! { |a, b| a <=> b }

    optimal_change = Hash.new do |hash, key|

      if key < coins.min
        hash[key] = []
      elsif coins.include?(key)
        hash[key] = [key]
      else
        hash[key] = coins
            .reject { |coin| coin > key }
            .map { |coin| [coin] + hash[key - coin] }
            .reject { |change| change.inject(&:+) != key }
            .min { |a, b| a.size <=> b.size } || []
      end

      puts hash
      hash[key]
    end

    optimal_change[amount].empty? ? -1 : optimal_change[amount].sort
end

另外一种方法是，创建一个数组，从1到amount，然后逐一用coin去替代，最后一个就是amount对应的coin了。

  def change(coins, total_change)
    return -1 if total_change < 0 || coins.any? { |x| x < 1 }
    m = [[]] + [nil] * total_change
    coins.size
         .times
         .to_a
         .product((1..m.size - 1).to_a)
         .each { |c, t|
           if coins[c] == t
             m[t] = [coins[c]]
           else
             (1..t - 1).select { |t2| coins[c] + t2 == t }
                       .reject { |t2| m[t2].nil? }
                       .each { |t2| 
                         m[t] = m[t2] + [coins[c]] if m[t].nil? || m[t2].size + 1 < m[t].size 
                       }
           end
         }
    m[-1].nil? ? -1 : m[-1]
  end