UVa 674: Coin Change

动态规划题。对于1,5,10,25,50五种币值的硬币，编号为0~4，存入数组cent中。数组iWay的元素iWay[k][i]表示仅使用0~i的硬币凑出k分钱的方法数，按是否使用编号为i的硬币分类，可得到状态转移方程iWay[k][i]=iWay[k][i-1]+iWay[k-cent[i]][i]。

一个优化的方法：分析可知取15,16,17,18,19分钱的方法数是相同的，因为它们的差距只在于1分的硬币数目。故iWay[k][i]=iWay[k/5*5][i]。这个式子可以稍微节省程序运行的时间。

我的解题代码如下：

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

#define MAX 7500

#define COINS 5

int cent[COINS] = { 1, 5, 10, 25, 50 };

int iWay[MAX][COINS];	//用0~i种硬币取k分钱的方法数iWay[k][k]=iWay[k][i-1]+iWay[k-cent[i]][i]

int f(int value, int coins)

{

	if(iWay[value][coins]) return iWay[value][coins];

	if(value>=cent[coins])	iWay[value][coins] = f(value,coins-1) + f(value-cent[coins], coins);

	else iWay[value][coins] = f(value,coins-1);

/*	for(int i=value/5*5; i<value/5*5+5; i++)

		iWay[i][coins] = iWay[value][coins];*///可用于优化程序

	return iWay[value][coins];

}

int main()

{

	int N;

	memset(iWay,0,sizeof(iWay));

	for(int i=0; i<COINS; i++) iWay[0][i] = 1;

	for(int i=0; i<MAX; i++) iWay[i][0] = 1;

	while(cin >> N)

	{

		cout << f(N,COINS-1) << endl;

	}

	return 0;

}