拼凑硬币问题

拼凑硬币问题

作者：Grey

原文地址：

博客园：拼凑硬币问题

CSDN：拼凑硬币问题

问题描述

现有 n1 + n2 种面值的硬币，其中前 n1 种为普通币，可以取任意枚，后 n2 种为纪念币， 每种最多只能取一枚（可能有重复值），每种硬币有一个面值，问能用多少种方法拼出 m 的面值?

题目链接见：牛客-拼凑硬币

主要思路

如果都用普通币，组合出 m 有多少种方法？假设得到 x 种方法。

如果都用纪念币，组合出 m 有多少种方法？假设得到 y 种方法。

如果是普通币 + 纪念币，组合出 m 有多少种方法？ 假设得到 z 种方法。

则 x + y + z 就是结果。

所以需要定义两个递归函数。

第一个递归函数：用纪念币，组成不同钱数的组合数量有多少

long[][] one(int[] arr, int money)
1

递归含义表示：用纪念币，返回组成不同钱数的组合数量有多少。由于纪念币每种最多只能选一个，所以这是一个经典的背包问题。

注：这个递归返回的是一个二维数组 dp，dp[i][j]表示 0 号到 i 号纪念币任意选择的情况下，组合出 m 有多少种方法。

递归含义确定后，二维数组 dp 的第 0 列的值已经可以很快确定，因为 dp[i][0] 表示 0 号到 i 号纪念币任意选择的情况下，组成 0 面值有多少方法。

显然只有一种方法，就是什么都不选，即

for (int i = 0; i < arr.length; i++) {
    dp[i][0] = 1;
}
1
2
3

dp[0][arr[0]] 的值也可以确定，因为 dp[0][arr[0]] 表示：0 号面值的纪念币，如何组成arr[0] 的面值，显然只有一种方法，就是选 0 号的面值，但是需要满足一个条件，即 arr[0] <= money，即

if (arr[0] <= money) {
    dp[0][arr[0]] = 1;
}
1
2
3

接下来就是普遍情况，对于任意 dp[i][j] 来说，首先可以有一种决策，不要 i 位置的纪念币，即

dp[i][j] = dp[i-1][j]
1

第二种决策，就是使用 i 位置的一枚纪念币，此时，要满足前提条件，即 arr[i] 位置的面值不能超过剩余面值

即：

dp[i][j] += j - arr[i] >= 0 ? dp[i - 1][j - arr[i]] : 0;
1

递归函数的完整代码如下

    public static long[][] one(int[] arr, int money) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        long[][] dp = new long[arr.length][money + 1];
        for (int i = 0; i < arr.length; i++) {
            dp[i][0] = 1;
        }
        if (arr[0] <= money) {
            dp[0][arr[0]] = 1;
        }
        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j <= money; j++) {
                dp[i][j] = dp[i - 1][j];
                dp[i][j] += j - arr[i] >= 0 ? dp[i - 1][j - arr[i]] : 0;
                dp[i][j] %= MOD;
            }
        }
        return dp;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

第二个递归函数：用普通币，组成不同钱数的组合数量有多少

long[][] many(int[] arr, int money)
1

递归含义表示：用普通币，组成不同钱数的组合数量有多少。也是返回一个二维数组 dp，dp[i][j]表示 0 号到 i 号普通币任意选择的情况下，组合出 m 有多少种方法。

根据递归含义，二维数组 dp 的第 0 列的值全为 1， 组成 0 面值的组合只有一种情况，就是用 0 枚普通币。即

for (int i = 0; i < arr.length; i++) {
    dp[i][0] = 1;
}
1
2
3

第 0 行也比较好确认，就是枚举 arr[0] 最多可以使用多少枚，即

for (int j = 1; arr[0] * j <= money; j++) {
    dp[0][arr[0] * j] = 1;
}
1
2
3

接下来是普遍位置，dp[i][j] 有两个决策，第一个决策，不使用 i 位置的普通币，即

dp[i][j] = dp[i-1][j]
1

第二个决策，使用 i 位置的普通币，此时，要满足前提条件，即 arr[i] 位置的面值不能超过剩余面值
即：

dp[i][j] += j - arr[i] >= 0 ? dp[i][j - arr[i]] : 0;
1

所以，递归函数的完整代码如下

    public static long[][] many(int[] arr, int money) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        long[][] dp = new long[arr.length][money + 1];
        for (int i = 0; i < arr.length; i++) {
            dp[i][0] = 1;
        }
        for (int j = 1; arr[0] * j <= money; j++) {
            dp[0][arr[0] * j] = 1;
        }
        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j <= money; j++) {
                dp[i][j] = dp[i - 1][j];
                dp[i][j] += j - arr[i] >= 0 ? dp[i][j - arr[i]] : 0;
                dp[i][j] %= MOD;
            }
        }
        return dp;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

整合函数，普通币和纪念币一起使用

有了上述两个 dp ，就可以很方便计算两种硬币一起使用过程的组合数量，核心思路就是这句

dpMany[dpMany.length - 1][i] * dpOne[dpOne.length - 1][money - i];
1

即：只用 普通币完成 i 面值的组合数量是 M，用纪念币完成 money - i 面值的组合数量是 N，则 M * N 就是两者一起用组合成 money 面值的组合数量。

这个整合函数的完整代码如下

    public static long moneyWays(int[] many, int[] one, int money) {
        if (money < 0) {
            return 0;
        }
        if ((many == null || many.length == 0) && (one == null || one.length == 0)) {
            return money == 0 ? 1 : 0;
        }
        long[][] dpMany = many(many, money);
        long[][] dpOne = one(one, money);
        if (dpMany == null) {
            return dpOne[dpOne.length - 1][money];
        }
        if (dpOne == null) {
            return dpMany[dpMany.length - 1][money];
        }
        long res = 0;
        for (int i = 0; i <= money; i++) {
            res += dpMany[dpMany.length - 1][i] * dpOne[dpOne.length - 1][money - i];
            res %= MOD;
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

完整代码

import java.util.Scanner;

public class Main {
    static int MOD = (int) 1e9 + 7;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n1 = in.nextInt();
        int n2 = in.nextInt();
        int target = in.nextInt();
        int[] many = new int[n1];
        int[] one = new int[n2];
        for (int i = 0; i < n1; i++) {
            many[i] = Integer.parseInt(in.next());
        }
        for (int i = 0; i < n2; i++) {
            one[i] = Integer.parseInt(in.next());
        }
        System.out.println(moneyWays(many, one, target));
        in.close();
    }

    public static long moneyWays(int[] many, int[] one, int money) {
        if (money < 0) {
            return 0;
        }
        if ((many == null || many.length == 0) && (one == null || one.length == 0)) {
            return money == 0 ? 1 : 0;
        }
        long[][] dpMany = many(many, money);
        long[][] dpOne = one(one, money);
        if (dpMany == null) {
            return dpOne[dpOne.length - 1][money];
        }
        if (dpOne == null) {
            return dpMany[dpMany.length - 1][money];
        }
        long res = 0;
        for (int i = 0; i <= money; i++) {
            res += dpMany[dpMany.length - 1][i] * dpOne[dpOne.length - 1][money - i];
            res %= MOD;
        }
        return res;
    }

    public static long[][] many(int[] arr, int money) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        long[][] dp = new long[arr.length][money + 1];
        for (int i = 0; i < arr.length; i++) {
            dp[i][0] = 1;
        }
        for (int j = 1; arr[0] * j <= money; j++) {
            dp[0][arr[0] * j] = 1;
        }
        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j <= money; j++) {
                dp[i][j] = dp[i - 1][j];
                dp[i][j] += j - arr[i] >= 0 ? dp[i][j - arr[i]] : 0;
                dp[i][j] %= MOD;
            }
        }
        return dp;
    }

    public static long[][] one(int[] arr, int money) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        long[][] dp = new long[arr.length][money + 1];
        for (int i = 0; i < arr.length; i++) {
            dp[i][0] = 1;
        }
        if (arr[0] <= money) {
            dp[0][arr[0]] = 1;
        }
        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j <= money; j++) {
                dp[i][j] = dp[i - 1][j];
                dp[i][j] += j - arr[i] >= 0 ? dp[i - 1][j - arr[i]] : 0;
                dp[i][j] %= MOD;
            }
        }
        return 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
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

更多

算法和数据结构笔记