題目敘述：https://zerojudge.tw/ShowProblem?problemid=d133
Virtual Judge: https://vjudge.net/problem/UVA-357
解題想法：DP, 零錢組合問題
- 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;
}