zerohou / algorithm Goto Github PK

问题：给定不同面额的硬币 coins 和一个总金额 amount。计算可以凑成总金额所需的组合数。如果没有任何一种硬币组合能组成总金额，返回 0。 
例 1:  coins = [1, 2, 5], amount = 5， result =4 (5=2+2+1=2+1+1+1=1+1+1+1)
例 2:  coins = [2], amount = 3, result = 0
说明:每种硬币的数量是无限的。

解法
一看到找零问题，马上反应用动态规划，只要知道<amount金额的解，就能马上得出金额为amount的解

时间复杂度
时间空间都是O(nm)