题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=2069
题意
有面值1,5,10,25,50的硬币数枚，对于输入的面值n，输出可凑成面值n（且限制总硬笔数小于等于100枚）的方案数。特别的，n=0时方案数=1。
其中，输入n<=250。
思路
DP。
状态 ways[j][i] 表示面值等于j且硬币枚数等于i时的方案数。
初始化时，只需将ways[0][0]=1即可，其他为0；
外层先遍历硬币面值种类，这层遍历的具体顺序不重要，即保证有不重复累加同样的组合即可；
中间层遍历硬币枚数，对从小到大硬币枚数，显然需正序；再遍历各种面值，这要正序，原理同完全背包；状态转移方程见代码。
最终输出答案时做相应的简单求和即可。
代码
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <set>
using namespace std;
#define MAX_MONEY 250
#define COIN_CNT 100
long long ways[MAX_MONEY+5][COIN_CNT+5];
int main(int argc, const char * argv[]) {
set<int> coin={1,5,10,25,50};
memset(ways, 0,sizeof(ways));
ways[0][0]=1;
for(auto it=coin.begin();it!=coin.end();++it){
for(int i=1;i<=COIN_CNT;++i){
for(int j=*it;j<=MAX_MONEY;++j){
ways[j][i]+=ways[j-*it][i-1];
}
}
}
int money;
while(~scanf("%d",&money)){
long long ans=0;
for(int i=0;i<=COIN_CNT;i++){
ans+=ways[money][i];
}
printf("%lld\n",ans);
}
return 0;
}