题目大意 给定一堆硬币和一个数字，求组成那个数字的最少硬币个数.如果币值没法构成给定数字，返回 -1
比如coins = [1, 2, 5], amount = 11，那么最少需要三枚硬币： (11 = 5 + 5 + 1)
解题思路：本题可以用动态规划和binary search来做。
动态规划：定义dp[i][j]表示用前i种硬币构成数字j的最少硬币个数。那么前i-1种硬币可以构成j-k * coin_i，都是合法的。所以dp[i][j] = min(dp[i][j], dp[i-1][j - k * coin_i]+ k ). 状态转移方程还有一个简化的版本：用前i个硬币构成j - coin_i，然后把coin_i加上就可以了。所以dp[i][j] = min(dp[i][j], dp[i][j - coin_i] + 1).
1. 动态规划，第一个写法
class Solution(object):
def coinChange(self, coins, amount):
dp = [float('inf') for _ in range(amount + 1)]
dp[0] = 0
for coin in coins:
for i in range(amount-coin, -1, -1):
if(dp[i] != float('inf')):
for k in range(1, amount + 1):
if k*coin + i <= amount:
dp[i+k*coin] = min(dp[i+k*coin], dp[i]+k)
if dp[amount] < float('inf'):
return dp[amount]
else:
return -1
2. 动态规划，第二种解法
class Solution(object):
def coinChange(self, coins, amount):
dp = [amount + 1 for _ in range(amount + 1)]
dp[0] = 0
for coin in coins:
for i in range(coin, amount + 1):
dp[i] = min(dp[i], dp[i - coin] + 1)
if dp[amount] >= amount + 1:
return -1
else:
return dp[amount]
3. dfs
第三种办法，dfs加强剪枝。首先把coins从大到小排列，先使用大的。如果剩余amount正好整除币值，就是一个合法解。
class Solution(object):
def coinChange(self, coins, amount):
coins = sorted(coins)[::-1]
self.ans = float('inf')
def dfs(coins, s, amount, count):
coin = coins[s]
# reach last coin
if s == len(coins) - 1:
if amount % coin == 0:
self.ans = min(self.ans, count + amount / coin)
else:
for k in range(amount/coin, -1, -1):
if count + k < self.ans:
# pruning, only search if new ans is less than current ans
dfs(coins, s + 1, amount - k*coin, count+k)
dfs(coins, 0, amount, 0)
if self.ans < float('inf'):
return self.ans
else:
return -1