322. 零钱兑换(中等)

Posted on In Views:

1，问题描述

322. 零钱兑换

难度：中等

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 2^31 - 1
  • 0 <= amount <= 10^4

2，初步思考

​ 这类问题都可以转换为：

​ 1，自上而下的递归

​ 2，自下而上的动态规划

3，代码处理

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
import java.util.Arrays;

public class _322零钱兑换 {

    // 解法：递归
    public int coinChange_recursion(int[] coins, int amount) {
        if (amount < 1) return 0;
        Arrays.sort(coins);
        return dfs(coins, amount, new int[amount]);
    }

    private int dfs(int[] coins, int amount, int[] dp) {
        if (amount == 0) {
            return 0;
        } else if (amount < 0) {
            return -1;
        }
        if (dp[amount - 1] != 0) return dp[amount - 1];// 直接使用缓存

        int min = Integer.MAX_VALUE;
        for (int coin : coins) {
            if (coin > amount) break;
            int res = dfs(coins, amount - coin, dp);
            if (res >= 0 && res < min) min = res + 1;
        }
        dp[amount - 1] = min == Integer.MAX_VALUE ? -1 : min;
        return min == Integer.MAX_VALUE ? -1 : min;
    }


    public int coinChange_2d(int[] coins, int amount) {
        int max = amount + 1;
        int len = coins.length;
        int[][] dp = new int[len + 1][amount + 1];
//        Arrays.fill(dp[:][0], max);
        for (int i = 1; i <= coins.length; i++) {
            for (int j = coins[i - 1]; j <= amount; j++) {
                dp[i][j] = dp[i - 1][j];
                if (coins[i - 1] <= j) {
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - coins[i - 1]] + 1);
                }
            }
        }
        return dp[len][amount] > amount ? -1 : dp[len][amount];
    }

    // 完全背包的方案数量
    // 背包容量为amount，最多可以放多重的硬币，求出最少的硬币数量
    public int coinChange_1d(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 <= coins.length; i++) {
            for (int j = coins[i - 1]; j <= amount; j++) {
                dp[j] = Math.min(dp[j], dp[j - coins[i - 1]] + 1);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }

    // 自上而下的递归
    public int coinChange_cache(int[] coins, int amount) {
        if (amount < 1) return 0;
        return coinChange(coins, amount, new int[amount]);
    }

    private int coinChange(int[] coins, int rem, int[] count) {
        if (rem < 0) return -1;
        if (rem == 0) return 0;
        if (count[rem - 1] != 0) return count[rem - 1];// 读取缓存

        int min = Integer.MAX_VALUE;
        for (int coin : coins) {
            int res = coinChange(coins, rem - coin, count);
            if (res >= 0 && res < min) min = 1 + res;
        }
        count[rem - 1] = (min == Integer.MAX_VALUE) ? -1 : min;
        return count[rem - 1];
    }

    public static void main(String[] args) {
        _322零钱兑换 change = new _322零钱兑换();
//        System.out.println(change.coinChange_recursion(new int[]{1, 2, 5}, 20));
//        System.out.println(change.coinChange_recursion(new int[]{1, 2, 5}, 11));
        System.out.println(change.coinChange_recursion(new int[]{474,83,404,3}, 264));
//        System.out.println(change.coinChange_recursion(new int[]{2}, 3));
    }
}

4，拓展知识点

背包问题类型：

01背包：每件物品只有一个

完全背包：每种物品有无限个

多重背包：每种物品有限定的个数，二进制优化

背包方案：有多少种背包方案可行

其他变形：例如多种容量问题