给定一组硬币的面额,其中包含面额 1
且相邻面额满足倍数关系,和一个目标金额 amount
。要求找出最少的硬币数目,使得硬币的总金额等于目标金额。如果无法组合成目标金额,返回 -1
。
题目描述:
给定一组不同面额的硬币(保证包含面额 1
且相邻面额是倍数关系),和一个目标金额 amount
,要求你找出最少的硬币数目,使得硬币的总金额等于目标金额。
要求:
-1
。输入格式:
n
,表示硬币的数量。1 ≤ n
≤ 20n
个整数,表示硬币的面额coins,保证每个面额都大于0且相邻的面额满足倍数关系,且包含面额 1
。1 ≤ coins[i]
≤ 109amount
,表示目标金额。1 ≤ amount
≤ 109输出格式:
-1
。示例:
输入:
5
1 5 10 20 100
66
输出:
5
说明:
20
+ 20
+ 20
+ 5
+ 1
,总金额为 11
,硬币数目为 3
。5
。