c317 - 硬幣問題！前傳

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算使用兩種硬幣（面值分別為 a 和 b）湊成金額 X 所需的最少硬幣數量。如果無法湊成，則輸出 -1。

解題思路

本題可以使用動態規劃 (Dynamic Programming) 解決。我們建立一個 dp 陣列，其中 dp[i] 表示湊成金額 i 所需的最少硬幣數量。初始化 dp 陣列的所有元素為 0，表示尚未找到湊成該金額的方法。

首先，我們使用面值為 a 的硬幣，將所有可以被 a 整除的金額的 dp 值初始化為所需的硬幣數量（即 i / a）。

然後，我們使用面值為 b 的硬幣，從金額 0 開始迭代到 x - b。對於每個金額 i，如果 dp[i] 有值（表示可以湊成金額 i），則檢查 dp[i + b] 是否有值。如果沒有，則將 dp[i + b] 初始化為 dp[i] + 1。如果已經有值，則將 dp[i + b] 更新為 min(dp[i + b], dp[i] + 1)。

最後，輸出 dp[x] 的值。如果 dp[x] 為 0，則表示無法湊成金額 x，輸出 -1。

複雜度分析

• 時間複雜度: O(x)
• 空間複雜度: O(x)

程式碼

#include <iostream>
using namespace std;
int main(){
	int t,x,a,b;
	cin >> t;
	while(t--){
		cin >> x >> a >> b;
		int dp[x+1]={0};
		for(int i=0;i*a<=x;++i)
			dp[a*i]=i;
		for(int i=0;i<=x-b;++i){
			if(dp[i]||i==0){
				if(dp[i+b]==0)
					dp[i+b]=dp[i]+1;
				else
					dp[i+b]=min(dp[i+b],dp[i]+1);
			}
		}
		if(dp[x])
			cout << dp[x] << "\n";
		else
			cout << "-1\n";
	}
}