Java实现如下：
public class Solution {
public int coinChange(int[] coins, int amount) {
if (amount == ) return ;
int[] dp = new int[amount + ];
dp[] = ;
for (int i = ;i <= amount ;i++ ) {
dp[i] = Integer.MAX_VALUE;
for(int k :coins) {
if(i>=k && dp[i-k] != Integer.MAX_VALUE) {
dp[i] = Math.min(dp[i-k] + ,dp[i]);
}
}
}
if(dp[amount]<Integer.MAX_VALUE && dp[amount] > ) {
return dp[amount];
} else {
return -;
}
}
}
补充一个python的实现：
import sys
class Solution:
def coinChange(self, coins: 'List[int]', amount: int) -> int:
dp = [sys.maxsize for i in range(amount+)]
dp[] =
for i in range(,amount+):
for k in coins:
if i >= k and dp[i-k] != sys.maxsize:
dp[i] = min(dp[i],dp[i-k]+) return - if dp[amount] == sys.maxsize else dp[amount]
注意内层循环范围是coins，而不要使用range(amount+1)，否则会TLE。DP方案执行时间：1700ms。
补充另一种解法，BFS + memo，效率要高一些，执行时间：1000ms。
class Solution:
def coinChange(self, coins: 'List[int]', amount: int) -> int:
n = len(coins)
if amount == :
return
target = {amount}
memo = set()
level =
result = amount +
while target:
cur = set()
for t in target:
if t not in memo:
memo.add(t)
for c in coins:
if t - c == :
result = min(result,level + )
#return level +
if t - c > :
cur.add(t - c)
target = cur
level +=
return - if result > amount else result
思路，使用memo记录已经“扩展”的节点，之后再遇到同样数值的节点，就不再扩展了(二叉树剪枝)。
target中存储当前层的节点，cur记录下一层的节点。
注意第16行，t - c == 0时，说明发现一种可以满足要求的方案，此时记录当前树的高度，并更新result。result中保存全局最小的满足条件的树的高度值。