leetcode 322：零钱兑换_给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金

leetcode 322：零钱兑换

322. 零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1
1
2
3

示例 2：

输入：coins = [2], amount = 3
输出：-1
1
2

示例 3：

输入：coins = [1], amount = 0
输出：0
1
2

提示：

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

Related Topics

广度优先搜索

数组

动态规划

思路1：动态规划

分析：dp[i]表示构建amount需要多少个硬币。

代码：

1. 给dp[i]填充amont+1。（因为不可能有amont+1个元素，表示无法填充）
2. 计算i构成需要多个硬币
   1. 遍历每个硬币
      1. 如果i大于这个硬币值，那么它需要的硬币数就是dp[i-硬币值]+1.

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 j = 0 ;  j < coins.length;j++){
                if(i >= coins[j]){
                    dp[i] = Math.min(dp[i],dp[i-coins[j]]+1);
                }
            }
        }
        return dp[amount] == amount+1 ? -1 : dp[amount];
    }
}
解答成功:
			执行耗时:12 ms,击败了81.00% 的Java用户
			内存消耗:40.8 MB,击败了37.81% 的Java用户
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

思路2：递归

我们要计算amount所需的最少数量，只需要计算F(S) = F(S-ci) + 1. S表示amont，ci表示每一个硬币值。

但是递归计算会计算很多重复的值，因此可以和思路1一样，使用一个数组存储这些值。

class Solution {
    public int coinChange(int[] coins, int amount) {

        return coinChange(coins,amount,new int[amount]);
    }
    public int coinChange(int[] coins,int amount,int[] count){
        if(amount < 0){
            return -1;
        }
        if(amount == 0){
            return 0;
        }
        //如果这个值已经计算过 直接返回
        if(count[amount-1]!=0){
            return count[amount-1];
        }
        //计算amont-硬币值(遍历每一个硬币) 所以的最少硬币 最后加1即可
        int min = Integer.MAX_VALUE;
        for(int coin : coins){
            int res = coinChange(coins,amount-coin,count);
            if(res >= 0 && res < min){
                min = res;
            }
        }
        count[amount-1] = min == Integer.MAX_VALUE ? -1 : min + 1;
        return count[amount-1];

    }

}
解答成功:
			执行耗时:28 ms,击败了12.14% 的Java用户
			内存消耗:41 MB,击败了25.68% 的Java用户
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
28
29
30
31
32
33