d253 - 00674 - Coin Change

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算給定金額 n cents 的硬幣組合方式數量，可以使用 penny (1 cent), nickel (5 cents), dime (10 cents), quarter (25 cents), 和 half-dollar (50 cents) 五種硬幣。

解題思路

此題可以使用動態規劃解決。程式碼中，a[i] 儲存了金額為 i cents 時的硬幣組合方式數量。程式碼利用陣列 a 預先計算了從 0 到 7489 的所有金額的組合方式數量。 程式碼的核心思想是，對於金額 i，其組合方式數量等於使用不同面額硬幣時的組合方式數量之和。 具體來說，a[i] += a[i-5] 表示在金額 i 的組合方式中，加上一個 5 cents 的硬幣，則剩餘金額為 i-5，其組合方式數量為 a[i-5]。 類似地，a[i] += a[i-10]、a[i] += a[i-25] 和 a[i] += a[i-50] 分別表示加上一個 10 cents、25 cents 和 50 cents 的硬幣。 初始條件是 a[0] = 1，表示金額為 0 時只有一種組合方式（不使用任何硬幣）。

複雜度分析

• 時間複雜度: O(n)，其中 n 是金額的最大值 (7489)。預計算陣列需要線性時間。
• 空間複雜度: O(n)，需要一個大小為 7490 的陣列 a 儲存中間結果。

程式碼

#include <stdio.h>
long long int a[7490],n;
int main(){
	for(int i=0;i<7490;++i)
		a[i]=1;
	for(int i=5;i<7490;++i)
		a[i]+=a[i-5];
	for(int i=10;i<7490;++i)
		a[i]+=a[i-10];
	for(int i=25;i<7490;++i)
		a[i]+=a[i-25];
	for(int i=50;i<7490;++i)
		a[i]+=a[i-50];
	while(scanf("%lld",&n)>0){
		printf("%lld\n",a[n]);
	}
}