题目描述
给定V种货币(单位:元),每种货币使用的次数不限。
不同种类的货币,面值可能是相同的。
现在,要你用这V种货币凑出N元钱,请问共有多少种不同的凑法。
输入格式
第一行包含两个整数V和N。
接下来的若干行,将一共输出V个整数,每个整数表示一种货币的面值。
输出格式
输出一个整数,表示所求总方案数。
数据范围
1≤V≤25,1≤N≤10000
样例
输入样例:
3 10
1 2 5
输出样例:
10
算法1
(DP未优化) $O(n^3)$
DP
状态标识f(i,j)
集合:用前i个货币,使得货币金额恰好为j的方案.
属性:方案.
状态计算
用k个货币i
f(i,j)=SUM(f(i-1,j)+f(i-1,j-m[i])+f(i-1,j-2m[i])+…+f(i-1,j-km[i])) km[i]<=j
时间复杂度
$O(n^3)$
Java 代码
import java.io.*;
import java.util.*;
class Main{
static final int N = 30, M = 10010;
static long[][] f = new long[N][M];
public static void main(String[] args){
Scanner sc = new Scanner(new BufferedInputStream(System.in));
int n=sc.nextInt(), m=sc.nextInt();
int[] q=new int[n+1];
for(int i=1;i<=n;++i) q[i]=sc.nextInt();
f[0][0]=1;
for(int i=1;i<=n;++i){
for(int j=0;j<=m;++j){
for(int k=0;k*q[i]<=j;++k){
f[i][j]+=f[i-1][j-k*q[i]];
}
}
}
System.out.println(f[n][m]);
sc.close();
}
}
算法2
(DP优化) $O(n^2)$
优化
f(i,j)=f(i-1,j)+f(i-1,j-m)+f(i-1,j-2m)+…+f(i-1,j-km)
f(i,j-m)= f(i-1,j-m)+f(i-1,j-2m)+…+f(i-1,j-km)
所以
f(i,j)=f(i-1,j)+f(i,j-m)
在用滚动数组优化
因为j-m<j 所以先更新前面
时间复杂度
$O(n^2)$
Java 代码
import java.io.*;
import java.util.*;
class Main{
static final int M = 10010;
static long[] f = new long[M];
public static void main(String[] args){
Scanner sc = new Scanner(new BufferedInputStream(System.in));
int n=sc.nextInt(), m=sc.nextInt();
int[] q=new int[n+1];
for(int i=1;i<=n;++i) q[i]=sc.nextInt();
f[0]=1;
for(int i=1;i<=n;++i){
for(int j=q[i];j<=m;++j){
f[j]=f[j]+f[j-q[i]];
}
}
System.out.println(f[m]);
sc.close();
}
}