【Leetcode】518.零钱兑换 II

518.零钱兑换 II

题目

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 

 

示例 1:
输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2:
输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。

示例 3:
输入: amount = 10, coins = [10] 
输出: 1

方法一（暴力递归）

例如：arr = [200, 100, 50, 20, 5, 1]，aim = 1000
对于第一个元素200：
选择0张200的，求出用后面的面值凑出1000的方法数
选择1张200的，求出用后面的面值凑出800的方法数
选择2张200的，求出用后面的面值凑出600的方法数
………
选择5张200的，求出用后面的面值凑出0的方法数

将以上方法数加起来，就是答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static int coins1(int[] arr, int aim) {
    if (arr == null || arr.length == 0 || aim < 0) {
        return 0;
    }
    return process1(arr, 0, aim);
}
//自由使用index及其之后所有的面值，凑成目标钱数aim的方法数
public static int process1(int[] arr, int index, int aim) {
    int res = 0;
    //递归结束条件：如果index来到了最后的位置，已经没有可选的面值了
    //如果这时目标钱数aim为0，则之前所选是一种方法。如果aim不为0，说明没有可选面值但还有钱没凑出来，说明之前所选不是一种可行方法。
    if (index == arr.length) {
        res = aim == 0 ? 1 : 0;
    } 
    else {
        //i表示使用几张arr[index]面值
        for (int i = 0; arr[index] * i <= aim; i++) 
            res += process1(arr, index + 1, aim - arr[index] * i);
    }
    return res;
}

方法二（动态规划）

由暴力递归改动态规划有如下几步：

  1. 分析可变参数，本题中返回值仅由aim和index两个参数决定。因此可变参数为2个。需要一个二维dp数组。

  2. 分析可变参数的变化范围：index的变化范围为数组arr的长度，aim的变化范围为0到aim这aim+1个值。分析完这前两步，我们就可以构造dp数组

    1
    2
    //dp[i][j]表示用arr中0到i个面值凑出钱数j的方法数
    int[][] dp = new int[arr.length][aim + 1];

  3. 确定Base Case: i为0和j为0时的情况

  4. 根据暴力递归的递归主体，分析出一个普遍位置是怎么依赖的。然后依次填充dp数组

代码

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
public int change(int aim, int[] arr) {
    //处理边界
    if(aim == 0)
        return 1;
    if (arr == null || arr.length == 0 || aim < 0) {
        return 0;
    }
    //构造dp数组
    int[][] dp = new int[arr.length][aim + 1];
    //设置base case
    for (int i = 0; i < arr.length; i++) {
        dp[i][0] = 1;
    }
    for (int j = 1; arr[0] * j <= aim; j++) {
        dp[0][arr[0] * j] = 1;
    }
    int num = 0;
    //填充dp数组
    for (int i = 1; i < arr.length; i++) {
        for (int j = 1; j <= aim; j++) {
            num = 0;
            for (int k = 0; j - arr[i] * k >= 0; k++) {
                num += dp[i - 1][j - arr[i] * k];
            }
            dp[i][j] = num;
        }
    }
    return dp[arr.length - 1][aim];
}