经典的DP题目,给你面值有1,5,10,25,50的币种,然后随意输入一个钱的数目,问用这些面值刚好凑成这个钱的方法有多少个
这道题目还可以用母函数做,但是背包更好做,仔细看一下题目的条件,最多会用100个钱币,所以可以直接先暴力预处理就可以了,
想好dp数组的含义就可以了,状态转移方程就是很简单的背包
#include<iostream> #include<cstdio> #include<list> #include<algorithm> #include<cstring> #include<string> #include<queue> #include<stack> #include<map> #include<vector> #include<cmath> #include<memory.h> #include<set> #define ll long long #define eps 1e-7 #define inf 0xfffffff const ll INF = 1ll<<61; using namespace std; //vector<pair<int,int> > G; //typedef pair<int,int > P; //vector<pair<int,int> > ::iterator iter; // //map<ll,int >mp; //map<ll,int >::iterator p; // ll dp[112][7500];//dp[i][j]当前使用i枚硬币,得到总价值为j的方法数 int value[6]={0,1,5,10,25,50}; void init() { memset(dp,0,sizeof(dp)); dp[0][0] = 1; for(int i=1;i<=5;i++) for(int j=1;j<=100;j++) for(int k=value[i];k<=7499;k++) dp[j][k] += dp[j-1][k-value[i]]; } int main() { int n; init(); while(cin>>n) { ll ans = 0; for(int j=0;j<=100;j++) ans += dp[j][n]; cout<<ans<<endl; } return EXIT_SUCCESS; }