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

# 題目說明

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

---

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

---

OUTPUT:
輸出N有幾種組合

# 解題方法

先建表，轉移方程為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/