# 【題解】ZeroJudge d133: 00357 – Let Me Count The Ways

Virtual Judge: https://vjudge.net/problem/UVA-357

• DP狀態值：可湊成該金額的硬幣組合數。
• DP初始值：0
• DP[0] = 1：零元有一種硬幣組合數（全部都不拿）。
• 檢視每一種硬幣，更新DP表格中，從該硬幣面值到目標金額的狀態值。
• 狀態轉移方程：dp[ j ] += dp[ j – coin[ i ] ]
• 檢查coin[ i ]時，可湊成 j 元的最新組合數 = 未使用 coin[ i ] 的組合數 dp[ j ] + 採用 coin[ i ] 的組合數 dp[ j – coin[ i ] ]。

Python 程式碼 (August 2019)

```n = 30000
lst = [0] * (n+1)
lst[0] = 1
for i in [1, 5, 10, 25, 50]:
for j in range(i, n+1):
lst[j] += lst[j-i]

while True:
try:
num = int(input())
if lst[num] == 1:
print('There is only 1 way to produce', num, 'cents change.')
else:
print('There are', lst[num], 'ways to produce', num, 'cents change.')
except:
break
```

C++ 程式碼 (December 2019)

```#include <iostream>
using namespace std;
long long dp[30001];

int main(){
int coin[] = {1, 5, 10, 25, 50};
dp[0] = 1;

for (int i=0; i<5; i++){
for (int j=coin[i]; j<30001; j++){
dp[j] += dp[j - coin[i]];
}
}
int n;
while (cin >> n){
if (dp[n] == 1)
cout << "There is only 1 way to produce " << n << " cents change.\n";
else
cout << "There are " << dp[n] << " ways to produce " << n << " cents change.\n";
}
return 0;
}
```