题目
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1：
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
示例 2：
输入: coins = [2], amount = 3
输出: -1
说明：
你可以认为每种硬币的数量是无限的。
答案分析
[2],4
1 -> 0, 2 -> 1, 3 -> 0, 4 -> 2
[1,2,5],11
1 -> 1, 2 -> 1, 3 -> 2, 4 -> 2, 5 -> 1, 6 -> 2, 7 -> 2, 8 -> 3, 9 -> 3, 10 -> 2, 11 -> 3
利用动态规划的思想，当前最优解可以通过前面的最优解得到，计算从1-amount的最优解，最后的值就是amount的最优解。
我的答案：
class Solution {
// [2],4
// 1 -> 0, 2 -> 1, 3 -> 0, 4 -> 2
// [1,2,5],11
// 1 -> 1, 2 -> 1, 3 -> 2, 4 -> 2, 5 -> 1, 6 -> 2, 7 -> 2, 8 -> 3, 9 -> 3, 10 -> 2, 11 -> 3
public int coinChange(int[] coins, int amount) {
if (amount < 1)
return 0;
int[] dp = new int[amount];
Arrays.fill(dp, 0);
for (int i=0; i<coins.length; i++) {
if (coins[i] <= amount) { // [1],1 #1、解答错误
dp[coins[i]-1] = 1;
}
}
for (int i=0; i<amount; i++) {
if (dp[i] == 0) {
dp[i] = Integer.MAX_VALUE;
for (int j=0; j<=i/2; j++) { // [259,78,94,130,493,4,168,149],4769, #2、超时
if (i-j-1 >=0 && dp[j] != 0 && dp[i-j-1] != 0) // [2],3 #3、数组越界
dp[i] = Math.min(dp[i], dp[j] + dp[i-j-1]);
}
if (dp[i] == Integer.MAX_VALUE) {
dp[i] = 0;
}
}
}
//System.out.println(Arrays.toString(dp));
return dp[amount-1] == 0 ? -1 : dp[amount-1];
}
}
182 / 182 个通过测试用例 执行用时：2555 ms
上面的时间复杂度是O(k*k)，发现不需要去遍历每个一个金额，只需看有没有对应的硬币就可以，有则加1，时间复杂度是O(kn)优化后的代码：
class Solution {
// [2],4
// 1 -> 0, 2 -> 1, 3 -> 0, 4 -> 2
// [1,2,5],11
// 1 -> 1, 2 -> 1, 3 -> 2, 4 -> 2, 5 -> 1, 6 -> 2, 7 -> 2, 8 -> 3, 9 -> 3, 10 -> 2, 11 -> 3
public int coinChange(int[] coins, int amount) {
if (amount < 1)
return 0;
int[] dp = new int[amount+1];
Arrays.fill(dp, 0);
for (int i=0; i<coins.length; i++) {
if (coins[i] <= amount) { // [1],1 #解答错误
dp[coins[i]] = 1;
}
}
for (int i=1; i<=amount; i++) {
if (dp[i] == 0) {
dp[i] = Integer.MAX_VALUE;
for (int j=0; j<coins.length; j++) { // [259,78,94,130,493,4,168,149],4769, #超时
if (coins[j] <= i && i-coins[j] >= 0 && dp[coins[j]] > 0 && dp[i-coins[j]] > 0)
dp[i] = Math.min(dp[i], 1 + dp[i-coins[j]]);
}
if (dp[i] == Integer.MAX_VALUE) {
dp[i] = 0;
}
}
}
//System.out.println(Arrays.toString(dp));
return dp[amount] == 0 ? -1 : dp[amount];
}
}
执行用时：24 ms
别人的答案：
class Solution {
int res = Integer.MAX_VALUE;
public int coinChange(int[] coins, int amount) {
Arrays.sort(coins);
helper(0, amount, coins, coins.length - 1);//递归调用，从尾向首递归调用，尽量使用大额硬币
return res == Integer.MAX_VALUE ? -1 : res;
}
//count是已经用了多少个硬币，amount是剩下金额，coins是硬币集合，n是第几种硬币
private void helper(int count, int amount, int[] coins, int start) {
if (amount == 0) { //找到一种组合
if (count < res) res = count;
return;//结束
}
if (start == -1 || amount / coins[start] + count >= res) return;//尝试失败，压根就不用进行后面的循环
for (int j = amount / coins[start]; j >= 0; j--) {//尽可能多的使用大硬币，
helper(count + j, amount - coins[start] * j, coins, start - 1);
}
}
}
执行用时：2 ms