扩展题
题目描述
给定 V 种货币(单位:元),每种货币使用的次数不限。
不同种类的货币,面值可能是相同的。
现在,要你用这 V 种货币凑出 N 元钱,请问共有多少种不同的凑法。
输入格式
第一行包含两个整数 V 和 N。
接下来的若干行,将一共输出 V 个整数,每个整数表示一种货币的面值。
输出格式
输出一个整数,表示所求总方案数。
数据范围
1≤V≤25,
1≤N≤10000
答案保证在long long范围内。
样例
输入样例:
3 10
1 2 5
输出样例:
10
j<v时:f[i][j]=f[i-1][j]+f[i][j-v];
j>=v时:f[i][j]=f[i-1]j
算法1:二维做法
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=30,M=10010;
int n,m;
LL f[N][M];
//dp:dp和dfs暴搜不同(dfs是枚举每种方案,dp是枚举每一类方案)
//闫氏dp分析法:
//1.状态表示f[i][j]:1)集合:所有从1~i中选,且总钱数是j的方案集合
// 2)属性:数量(结合题目,eg min,max....)
//2.状态计算:--即--->集合划分(见图)
//完全背包问题
//二维做法
int main(){
cin>>n>>m;
f[0][0]=1;
for(int i=1;i<=n;i++){//枚举到1~i的货币中选总钱数为j的集合
int v;
cin>>v;
for(int j=0;j<=m;j++)//集合划分f[i][j],再推导公式,就可得出下面式子
{
f[i][j]=f[i-1][j];//从1~i种货币中选,且总钱数为j,且第i种货币
//不拿的方案数等于前面f[i-1][j](此时j<v)
if(j>=v)f[i][j]+=f[i][j-v];//若j>=v,则存在f[i][j-v],
//且此时的f[i][j]其实是等于f[i-1][j]+f[i][j-v]
}
}
cout<<f[n][m]<<endl;
return 0;
}
算法2:一维做法
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=30,M=10010;
int n,m;
LL f[M];
//一维做法(其实和二维类似)
int main(){
cin>>n>>m;
f[0]=1;
for(int i=1;i<=n;i++){//在面值为i的集合中
int v;
cin>>v;
for(int j=v;j<=m;j++)//在1~i中取到价值总和为j,
f[j]+=f[j-v];
// f[i][j]<--| |——>f[i-1][j](未更新的)
}
cout<<f[m];//f[m]--即-->f[n][m](i已经结束了循环,f[n][m]恰好更新完)
return 0;
}