d904 - 換零錢
題目描述
題目要求計算使用給定的 N 種硬幣，湊成 C 美分的最佳情況下所需的最小硬幣數量。最佳情況指的是使用最少的硬幣數量。
解題思路
本題可以使用動態規劃來解決。定義 sum[i] 為湊成 i 美分所需的最小硬幣數量。初始化 sum[m] = 1，其中 m 是目標金額。然後，對於每種硬幣，從金額 m 開始反向迭代到 0，如果使用該硬幣可以湊成 i - n 美分，則更新 sum[i - n] 的值。最後，sum[0] - 1 就是湊成目標金額所需的最小硬幣數量。之所以減 1 是因為 sum[m] 初始化為 1，代表湊成金額 m 需要 1 個硬幣（實際上是需要計算從 0 到 m 的最小硬幣數）。
複雜度分析
- 時間複雜度: O(C * N)
- 空間複雜度: O(C)
程式碼
#include <iostream>
using namespace std;
int main(){
int m,a;
while(cin >> m >> a){
int sum[m+1]={0},n;
sum[m]=1;
while(a--){
cin >> n;
for(int i=m;i>=0;i--){
if(sum[i]!=0&&i-n>=0){
if(sum[i-n]==0)
sum[i-n]=sum[i]+1;
else if(sum[i-n]!=0&&sum[i-n]>sum[i]+1)
sum[i-n]=sum[i]+1;
}
}
}
cout << sum[0]-1;
}
}