HDU 2069 Coin Change

思路：

1.设dp[i][j]表示用i个硬币可以组成j元的种数；
2.我们需要避免出现类似5+1和1+5这种同一情况的重复计算，因此我们分先后次序依次递推所有面值的硬币（即将对面值的遍历放到循环最外圈）；
3.设coin[k]是当前遍历到的面值，我们可以得到递推关系dp[i][j]=dp[i][j]+dp[i-1][j-coin[k]]；

代码：

#include<iostream>
using namespace std;
const int N=5;
const int MAX_N=101;
const int MAX_S=251;
int dp[MAX_N][MAX_S];     //dp[i][j]用i个硬币组成jcents的方法数
int coin[N]={1,5,10,25,50};
int rs[MAX_S];
void init(){
	for(int k=0;k<N;k++){
		dp[1][coin[k]]++;
		for(int i=2;i<MAX_N;i++){
			for(int j=coin[k]+1;j<MAX_S;j++){
				dp[i][j]+=dp[i-1][j-coin[k]];
			}
		}
	}
	for(int i=1;i<MAX_S;i++){
		for(int j=1;j<MAX_N;j++) rs[i]+=dp[j][i];
	}
} 
int main(){
	init();
	int n;
	while(~scanf("%d",&n)){
		if(!n) puts("1");
		else printf("%d
",rs[n]);
	}
	return 0;
}