[UVa]357:Let Me Count The Ways

這題是DP的找零錢問題。

有幾種組合的算法，
由於可能會有重覆算到的關係，
所以要先加入最小的零錢(此題是1cent)進去，
看看各個值(小於等於30000)假設最後一枚硬幣為此零錢能用幾種方法(其實是dp[該值-加入的零錢價值]種)找出來，
接著再把次小的零錢(此題是5cents)放進去，
看看各個值(小於等於30000)假設最後一枚硬幣為此零錢能用幾種方法(其實是dp[該值-加入的零錢價值]種)找出來，
這樣以此類推到最大的零錢，
這樣我在算最後一個零錢是5cents的組合的時候，
我只會找出1cent跟5cents的組合，
不會找出配上10cents啦...25cents啦...或是50cents之類的組合。
等到我在算最後一個零錢是10cents的組合的時候，
我只會找出10cents跟5cents跟1cent的組合，
不會找出配上25cents啦...或是50cents之類的組合。
(如果看不懂以上內容，可以翻閱關於DP找零錢問題的教學文章。)

P.S. 這題要用long long Orz...

[C](0.020)

	#include<stdio.h>
	int main()
	{
	long long dp[30005] = {1};
	int money[5] = {1, 5, 10, 25, 50};
	int i, j;
	for( i = 0 ; i < 5 ; i++ )
	for( j = money[i] ; j <= 30000 ; j++ )
	dp[j] += dp[j-money[i]];
	int cents;
	while( scanf( "%d", &cents ) != EOF )
	if( dp[cents] == 1 )
	printf( "There is only 1 way to produce %d cents change.\n", cents );
	else
	printf( "There are %lld ways to produce %d cents change.\n", dp[cents], cents );
	return 0;
	}

view raw UVa357.c hosted with ❤ by GitHub