来自Leetcode第322题零钱兑换
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1:
1
2
3
| 输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
|
贪心
从面额最大的货币开始找零，并遍历完当前硬币数组，当剩余金额为0时返回上层搜索，当目前已用总数大于已知最小硬币数时也返回。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
int[] coin;
int ans = Integer.MAX_VALUE;
public int coinChange(int[] coins, int amount) {
Arrays.sort(coins);
this.coin = coins;
dfs(coin.length-1,amount,0);
return ans == Integer.MAX_VALUE ? -1 : ans;
}
private void dfs(int index,int amount,int count){
if(index < 0)
return ;
int rest,tmp_count;
for(int i = amount /coin[index];i >= 0;i--){
rest = amount - i * coin[index];
tmp_count = count + i;
if(rest == 0){
ans = Math.min(ans,tmp_count);
break;
}
if(tmp_count + 1 >= ans)
break;
dfs(index-1,rest,tmp_count);
}
}
}
|
动态规划
来自官方题解
仍定义 F(i) 为组成金额 i 所需最少的硬币数量，假设在计算 F(i) 之前，我们已经计算出 F(0)−F(i−1) 的答案。 则 F(i) 对应的转移方程应为
其中 $c_j$代表的是第 j 枚硬币的面值，即我们枚举最后一枚硬币面额是 $c_j$，那么需要从 $i-c_j$ 这个金额的状态 $F(i-c_j)$转移过来，再算上枚举的这枚硬币数量 1 的贡献，由于要硬币数量最少，所以 $F(i$)为前面能转移过来的状态的最小值加上枚举的硬币数量 1 。
例子1：假设
1
| coins = [1, 2, 5], amount = 11
|
则，当 $i==0$ 时无法用硬币组成，为 0 。当 $i<0$时，忽略 $F(i)$
| F(i) |
最小硬币数量 |
| F(0) |
0 //金额为0不能由硬币组成 |
| F(1) |
1 //$F(1)=min(F(1-1),F(1-2),F(1-5))+1=1$ |
| F(2) |
1 //$F(2)=min(F(2-1),F(2-2),F(2-5))+1=1$ |
| F(3) |
2 //$F(3)=min(F(3-1),F(3-2),F(3-5))+1=2$ |
| F(4) |
2 /$/F(4)=min(F(4-1),F(4-2),F(4-5))+1=2$ |
| … |
… |
| F(11) |
3 //$F(11)=min(F(11-1),F(11-2),F(11-5))+1=3$ |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| public class Solution {
public int coinChange(int[] coins, int amount) {
int max = amount + 1;
int[] dp = new int[amount + 1];
Arrays.fill(dp, max);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}
|