UVa 674 Coin Change

想法：
    用method[i]=k表示i元有k種方法，枚舉所有錢幣，假設該錢幣為j元，則method[i+j] = method[i+j] + method[j]，表示method[i+j]的一部分方法數是由method[j]而來。

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	int method[10000] = {0};
	int cent[5] = {1, 5, 10, 25, 50};
	int main()
	{
	// 建表
	method[0] = 1;
	for (int i = 0; i < 5; ++i) {
	for (int j = 0; j + cent[i] <= 7490; ++j)
	method[j+cent[i]] += method[j];
	}
	// input & output
	int n;
	while (scanf("%d", &n) != EOF)
	printf("%d\n", method[n]);
	}

view raw [UVa] 674 Coin Machine.cpp hosted with ❤ by GitHub