拼湊硬幣問題
拼湊硬幣問題
作者：Grey
原文地址：
問題描述
現有 n1 + n2 種面值的硬幣，其中前 n1 種為普通幣，可以取任意枚，後 n2 種為紀念幣， 每種最多只能取一枚（可能有重複值），每種硬幣有一個面值，問能用多少種方法拼出 m 的面值?
題目鏈接見：牛客-拼湊硬幣
主要思路
如果都用普通幣，組合出 m 有多少種方法？假設得到 x 種方法。
如果都用紀念幣，組合出 m 有多少種方法？假設得到 y 種方法。
如果是普通幣 + 紀念幣，組合出 m 有多少種方法？ 假設得到 z 種方法。
則 x + y + z 就是結果。
所以需要定義兩個遞歸函數。
第一個遞歸函數：用紀念幣，組成不同錢數的組合數量有多少
long[][] one(int[] arr, int money)
遞歸含義表示：用紀念幣，返回組成不同錢數的組合數量有多少。由於紀念幣每種最多只能選一個，所以這是一個經典的背包問題。
註：這個遞歸返回的是一個二維數組 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;
}
dp[0][arr[0]] 的值也可以確定，因為 dp[0][arr[0]] 表示：0 號面值的紀念幣，如何組成arr[0] 的面值，顯然只有一種方法，就是選 0 號的面值，但是需要滿足一個條件，即 arr[0] <= money，即
if (arr[0] <= money) {
dp[0][arr[0]] = 1;
}
接下來就是普遍情況，對於任意 dp[i][j] 來說，首先可以有一種決策，不要 i 位置的紀念幣，即
dp[i][j] = dp[i-1][j]
第二種決策，就是使用 i 位置的一枚紀念幣，此時，要滿足前提條件，即 arr[i] 位置的面值不能超過剩餘面值
即：
dp[i][j] += j - arr[i] >= 0 ? dp[i - 1][j - arr[i]] : 0;
遞歸函數的完整程式碼如下
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;
}
第二個遞歸函數：用普通幣，組成不同錢數的組合數量有多少
long[][] many(int[] arr, int money)
遞歸含義表示：用普通幣，組成不同錢數的組合數量有多少。也是返回一個二維數組 dp，dp[i][j]表示 0 號到 i 號普通幣任意選擇的情況下，組合出 m 有多少種方法。
根據遞歸含義，二維數組 dp 的第 0 列的值全為 1， 組成 0 面值的組合只有一種情況，就是用 0 枚普通幣。即
for (int i = 0; i < arr.length; i++) {
dp[i][0] = 1;
}
第 0 行也比較好確認，就是枚舉 arr[0] 最多可以使用多少枚，即
for (int j = 1; arr[0] * j <= money; j++) {
dp[0][arr[0] * j] = 1;
}
接下來是普遍位置，dp[i][j] 有兩個決策，第一個決策，不使用 i 位置的普通幣，即
dp[i][j] = dp[i-1][j]
第二個決策，使用 i 位置的普通幣，此時，要滿足前提條件，即 arr[i] 位置的面值不能超過剩餘面值
即：
dp[i][j] += j - arr[i] >= 0 ? dp[i][j - arr[i]] : 0;
所以，遞歸函數的完整程式碼如下
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;
}
整合函數，普通幣和紀念幣一起使用
有了上述兩個 dp ，就可以很方便計算兩種硬幣一起使用過程的組合數量，核心思路就是這句
dpMany[dpMany.length - 1][i] * dpOne[dpOne.length - 1][money - i];
即：只用 普通幣完成 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;
}
完整程式碼
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;
}
}
