# 題目: UVa 357 - Let Me Count The Ways

# 題目說明

有 5 種不同面額的幣值， 1、5、10、25、50
給一個 N ，求由以上幣值組合成 N 共有幾種方法數

INPUT:
每筆資料輸入一個整數 N

OUTPUT:
輸出 N 有幾種組合

此題為 Coin Change 問題

先建表，轉移方程為 coin[i] += coin[i - j]
其中 i 為當前的 N ， j 為幣值
之後查表輸出即可

	#include <iostream>

	using namespace std;

	int main()
	{
	ios::sync_with_stdio(false);
	cout.tie(nullptr);
	cin.tie(nullptr);

	int N;
	long long coin[30001]{};
	int dif[] = { 1, 5, 10, 25, 50 };

	coin[0] = 1;
	for (auto& j : dif) for (int i = j; i <= 30000; ++i) coin[i] += coin[i - j];

	while (cin >> N)
	{
	if (coin[N] == 1) cout << "There is only 1 way to produce " << N << " cents change.\n";
	else cout << "There are " << coin[N] << " ways to produce " << N << " cents change.\n";
	}

	return 0;
	}

https://www.larrysprognotes.com/UVa-357/