题目描述
blablabla
样例
import java.util.Scanner;
public class Main {
static int N,V;
static long[][] men = new long[30][10000+10];
static long[] f = new long[10000+10];
static int[] faceValue;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
V = scanner.nextInt();
N = scanner.nextInt();
faceValue = new int[V+1];
for (int i = 1; i <= V; i++) {
faceValue[i] = scanner.nextInt();
}
f[0]=1;
for (int i = V; i >=1; i--) {
for (int j = 1; j <=N ; j++) {
if (j >= faceValue[i]){
f[j] = f[j] + f[j - faceValue[i]]; //,可以选择是否选取该硬币,组合数量等于不选取该硬币时的组合数量加上选取该硬币时的组合数量
}
}
}
System.out.print(f[N]);
}
public static long dfs(int x,int syN){
if (men[x][syN] !=0) return men[x][syN];
if (syN==0) return men[x][syN]=1;
if (x>V) return 0;
if (syN<faceValue[x]) men[x][syN]= dfs(x+1, syN);
else men[x][syN]= dfs(x+1, syN)+dfs(x, syN-faceValue[x]);
return men[x][syN];
}
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla