零钱兑换

给你一个整数数组 coins，表示不同面额的硬币；以及一个整数 amount，表示总金额。

计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

约定

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 2^31 - 1
• 0 <= amount <= 10^4
• 每种硬币的数量无限。

输入

• coins：硬币面额数组
• amount：目标总金额

输出

凑成 amount 所需的最少硬币数；无法凑出时返回 -1。

示例一

输入：

coins = [1, 2, 5], amount = 11

输出：

3

解释：11 = 5 + 5 + 1。

示例二

输入：

coins = [2], amount = 3

输出：

-1

示例三

输入：

coins = [1], amount = 0

输出：

0

复杂度要求

• 时间复杂度：O(amount * n)，n 为硬币种数
• 空间复杂度：O(amount)