题目
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回-1。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3
输出：-1
示例 3：
输入：coins = [1], amount = 0
输出：0
示例 4：
输入：coins = [1], amount = 1
输出：1
示例 5：
输入：coins = [1], amount = 2
输出：2
提示：
1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104
方法
记忆化搜索（从大到小）
从amount金额数逐次减去面额的大小，即从大数计算到小数，在计算的过程中会遇到计算过的金额，我们引入了数组保存已经算过的值，减少了时间复杂度
- 时间复杂度：O(S*n)，S是amount金额数，n为coins的长度即面额数
- 空间复杂度：O(S)
public class Solution {
public int coinChange(int[] coins, int amount) {
if(amount<1){
return 0;
}
return coinChange1(coins,amount,new int[amount]);
}
private int coinChange1(int[] coins,int resAmount,int[] minArr){
if(resAmount<0){
return -1;
}
if(resAmount==0){
return 0;
}
if(minArr[resAmount-1]!=0){
return minArr[resAmount-1];
}
int min = Integer.MAX_VALUE;
for(int c:coins){
int res = coinChange1(coins,resAmount-c,minArr);
if(res>=0&&res+1<min){
min = res+1;
}
}
minArr[resAmount-1] = min==Integer.MAX_VALUE? -1:min;
return minArr[resAmount-1];
}
}
动态规划（从小到大）
用dp数组保存每种金额的最小个数，从面额开始计算到总金额数，利用了计算过的小金额结果，去除重复计算
- 时间复杂度：O(S*n)，S是amount金额数，n为coins的长度即面额数
- 空间复杂度：O(S)
public class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount+1];
Arrays.fill(dp,amount+1);
dp[0] = 0;
for(int i=1;i<=amount;i++){
for(int c:coins){
if(c<=i){
dp[i] = Math.min(dp[i],dp[i-c]+1);
}
}
}
return dp[amount]>amount?-1:dp[amount];
}
}