d119 - 有獎徵答：換零錢
題目描述
題目要求計算給定金額的所有零錢組合數，零錢面額為 1, 5, 10, 20, 50, 100, 200, 500, 1000, 2000。需要注意的是，題目要求排除輸入金額本身所使用的零錢組合。
解題思路
此題可以使用動態規劃來解決。程式碼中，a[i] 儲存了組成金額 i 的零錢組合數。程式碼預先計算了從 0 到 50000 的所有金額的組合數，然後對於每個輸入金額，直接從預先計算的 a 陣列中獲取結果，並減去 1 (排除輸入金額本身所使用的零錢組合)。
預計算的過程，實際上是使用貪心策略，逐步增加可用的零錢面額，並更新 a 陣列。例如，先使用 1, 5，再使用 1, 5, 10，以此類推。
複雜度分析
- 時間複雜度: O(50000 + n)，其中 n 是輸入的組數。預計算陣列
a的時間複雜度為 O(50000)，處理每組輸入的時間複雜度為 O(1)。 - 空間複雜度: O(50001)，用於儲存
a陣列。
程式碼
#include <iostream>
#include <string>
using namespace std;
long long int a[50001];
int main(){
for(int i=0;i<50001;++i)
a[i]=1;
for(int i=5;i<50001;++i)
a[i]+=a[i-5];
for(int i=10;i<50001;++i)
a[i]+=a[i-10];
for(int i=20;i<50001;++i)
a[i]+=a[i-20];
for(int i=50;i<50001;++i)
a[i]+=a[i-50];
for(int i=100;i<50001;++i)
a[i]+=a[i-100];
for(int i=200;i<50001;++i)
a[i]+=a[i-200];
for(int i=500;i<50001;++i)
a[i]+=a[i-500];
for(int i=1000;i<50001;++i)
a[i]+=a[i-1000];
for(int i=2000;i<50001;++i)
a[i]+=a[i-2000];
string g;
while(getline(cin,g)){
if(g=="0")break;
int sum=0,x=0;
for(int i=0,gl=g.length();i<gl;++i){
if(g[i]!=' '){
x*=10;
x+=g[i]-'0';
}
else{
sum+=x;
x=0;
}
}
sum+=x;
cout << a[sum]-1 << "\n";
}
}