拼凑硬币

[编程题]拼凑硬币

热度指数：528 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 1024M，其他语言2048M
算法知识视频讲解

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

输入描述:

第一行输入三个整数n1,n2,m        n1,n2<=1000 m<=100000
第二行输入n1个整数表示普通币的面值
第三行输入n2个整数表示纪念币的面值
不同的硬币面值可能相同

输出描述:

使用编号不同但面值相同的硬币算不同的拼法
输出用多少种方法拼出m的面值，由于答案过大，对1e9 + 7取模

示例1

输入

5 5 100
87 76 15 79 53 
1 94 59 30 5

输出

说明

1+94+5
79+15+5+1

算法知识视频讲解

Java

牛客982480680号

import java.util.Scanner;
// 一维DP的优化
public class Main {
static int MOD = (int)(1e9 + 7);
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
int l1 = in.nextInt();
int l2 = in.nextInt();
int[] nums1 = new int[l1];
int[] nums2 = new int[l2];
int aim = in.nextInt();
for (int i = 0; i < l1; i++){
nums1[i] = in.nextInt();
}
for (int i = 0; i < l2; i++){
nums2[i] = in.nextInt();
}
long res = 0;
if (l1 == 0 && l2 == 0){
res = aim == 0 ? 1:0;
System.out.print(res);
}
long[] dp1 = allBagFunc(nums1, aim);
long[] dp2 = zeroOneBagFunc(nums2, aim);
for ( int i = 0; i <= aim; i++){
res += dp1[i] * dp2[aim-i];
res %= MOD;
}
System.out.print(res);
}
public static long[] allBagFunc(int[] arr, int aim){
long[] dp = new long[aim+1];
dp[0] = 1;
for (int num: arr){
for (int i = num; i <= aim; i++){
dp[i] += dp[i-num];
dp[i] %= MOD;
}
}
return dp;
}
public static long[] zeroOneBagFunc(int[] arr, int aim){
long[] dp = new long[aim+1];
dp[0] = 1;
for (int num: arr){
for (int i = aim; i >= num; i--){
dp[i] += dp[i-num];
dp[i] %= MOD;
}
}
return dp;
}
}

发表于 2023-11-17 15:18:42 回复(0)