UVaOJ-674 Coin Change (完全背包)

题意：

有1,5,10,25,50五种硬币，给出一个金额，问有几种凑钱的方式。

思路：

递推；

首先将dp数组全部初始化为0， dp[0] = 1，dp[i]表示“面值i凑钱种数”;

for (i = 0; i < 5; i ++){ // 代表5种面值的硬币，当前选用前i种
for(j = 0; j < N - 100; j ++){ // j代表面值

。。。。。。 // 更新每个面值的凑钱种数

}
}

那个实例来说：

i = 1时，dp数组存放了只有1元和5元的硬币时，各个面值的钱的凑钱方式；

现在i = 2，我们要新加入一种面值为10的硬币；

dp[j] 是原先时只用1,5两种硬币凑出j元的方案数，再加上必须含有10元凑出j元的方案数，就是1,5,10三种硬币的凑出j元方案数！但如何求出新加入这种面值的硬币的凑钱种数呢？

先说状态转移方程 dp[j] = dp[j] + dp[j - coin[i]]；

dp[j - coin[i]] 是1,5,10三种硬币凑出j - coin[i]元的方案数，当然这里面也含有只有1，5两种硬币的情况，可是注意这儿我们要凑出j元，还需要再加一个coin[i]（即10元），而加上这个金额，方案数目是不变的，因此，dp[j - coin[i]]即是必须含有10元凑出j元的方案数了。

代码：

#include 
  
   
#define N 8000
int coin[5] = {1, 5, 10, 25, 50};
int dp[N] = {1};

int main()
{
	int i, j, n;
	for (i = 0; i < 5; i ++){
		for(j = 0; j < N - 100; j ++)
			dp[j + coin[i]] += dp[j];
	}

	while (scanf("%d", &n) != EOF)
		printf("%d\n", dp[n]);

	return 0;
}