322. 零钱兑换

题目描述

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

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

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

输入输出

1
2
3
4
5
6
7
8
9
输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

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

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

基本思路

  1. 递归：暴力 递归搜索
  2. 记忆化搜索：大佬题解
  3. 动态规划：官方题解
  4. 性能：
    1. 时复：O(Sn)。其中 S 是金额，n 是面额数。我们一共需要计算 O(S) 个状态，S 为题目所给的总金额。对于每个状态，每次需要枚举 n 个面额来转移状态，所以一共需要 O(Sn) 的时间复杂度。
    2. 空复：O(S)。数组 dp 需要开长度为总金额 S 的空间。

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
// 递归 超出时间限制
class Solution {
    int res = Integer.MAX_VALUE;
    public int coinChange(int[] coins, int amount) {
        if(coins.length == 0){
            return -1;
        }
        findways(coins, amount, 0);
        if(res == Integer.MAX_VALUE){
            return -1;
        }
        return res;
    }

    public void findways(int[] coins, int amount, int count){
        if(amount < 0) return;
        if(amount == 0){
            res = Math.min(count, res);
        }
        for(int i = 0; i < coins.length; i++){
            findways(coins, amount-coins[i], count+1);
        }
    }
}

// 记忆化搜索 通过
class Solution {
    int[] memo;
    //memo[n] 表示钱币n可以被换取的最少的硬币数，不能换取就为 -1
    public int coinChange(int[] coins, int amount) {
        if(coins.length == 0){
            return -1;
        }
        memo = new int[amount];
        return findways(coins, amount);
    }

    public int findways(int[] coins, int amount){
        if(amount < 0) return -1;
        if(amount == 0) return 0;
        if(memo[amount-1] != 0){
            return memo[amount-1];
        }

        int min = Integer.MAX_VALUE;
        for(int i = 0; i < coins.length; i++){
            int res = findways(coins, amount-coins[i]);
            if(res >= 0 && res < min){
                min = res + 1;
            }
        }
        memo[amount - 1] = (min == Integer.MAX_VALUE ? -1 : min);
        return memo[amount-1];
    }
}

// 动态规划 通过
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];
    }
}