UVA - 674 Coin Change 经典问题

题目大意：给出5中硬币，分别是1，5，10，25，50，然后给你一个数字，能由这五种硬币组成的方式有多少种

解题思路：解法一：硬币按小到大排，用j表示还有能用几种硬币表示，则当j==0时，则表示所剩下的值可以用n个1来表示，具体看代码

#include<cstdio>
const int maxn = 7500;
int coin[5] = {1,5,10,25,50};
int s[maxn][5],n;

int dp(int i, int j) {

	if(j == 0)
		return s[i][j] = 1;

	if(s[i][j] > 0)	
		return s[i][j];

	for(int k = 0; k <= i; k += coin[j]) 
		s[i][j] = s[i][j] + dp(i-k,j-1);
	
	return s[i][j];	
}

int main() {
	while(scanf("%d", &n) != EOF)  {
		printf("%d\n", dp(n,4));
	}
	return 0;	
}

解法二：滚动数组的打表法，用dp[i]表示i能有几种表示方式，则dp[i] = dp[i] + dp[i-coin[j]]，第二个dp[i]表示的是再第j种硬币之前的i能有几种表示方式

#include<cstdio>
#include<cstring>

int dp[7500] = {0};
int coin[5] = {50,25,10,5,1};

int main() {
	dp[0] = 1;
	for(int i = 0 ; i < 5; i++)
		for(int j = coin[i]; j < 7500; j++)
			dp[j] += dp[j-coin[i]];
	int num;
	while(scanf("%d",&num) != EOF)
		printf("%d\n",dp[num]);
}