d133 - 00357 - Let Me Count The Ways

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算給定金額 n (0 <= n <= 30000) 有多少種不同的硬幣組合可以湊成該金額。可用的硬幣面值為 1 (penny), 5 (nickel), 10 (dime), 25 (quarter), 和 50 (half-dollar) cents。

解題思路

這題可以使用動態規劃 (Dynamic Programming) 來解決。定義 a[i] 為湊成金額 i 的硬幣組合數。初始化 a[0] = 1 (湊成 0 元的方法只有一種，就是不使用任何硬幣)。然後，對於每種硬幣面值 (1, 5, 10, 25, 50)，我們迭代所有大於或等於該面值的金額，並更新 a[i] 的值。具體來說，a[i] += a[i - coin]，其中 coin 是當前考慮的硬幣面值。

程式碼中，為了優化效能，直接預先計算了 a[0] 到 a[30000] 的值，避免了在每次輸入時重新計算。程式碼中使用了 1, 5, 10, 25, 50 五種硬幣，分別進行了五次迴圈，每次迴圈更新 a[i] 的值。

複雜度分析

• 時間複雜度: O(n) (預先計算所有金額的組合數)
• 空間複雜度: O(n) (儲存 a 陣列)

程式碼

#include <stdio.h>
long long int a[30001],n;
int main(){
	for(int i=0;i<30001;++i)
		a[i]=1;
	for(int i=5;i<30001;++i)
		a[i]+=a[i-5];
	for(int i=10;i<30001;++i)
		a[i]+=a[i-10];
	for(int i=25;i<30001;++i)
		a[i]+=a[i-25];
	for(int i=50;i<30001;++i)
		a[i]+=a[i-50];
	while(scanf("%lld",&n)>0){
		if(a[n]==1)
			printf("There is only 1 way to produce %lld cents change.\n",n);
		else
			printf("There are %lld ways to produce %lld cents change.\n",a[n],n);
	}
}