亚马逊面试题：最少硬币凑金额问题（动态规划 / BFS）

You are given an integer array coins representing coin denominations, and an integer amount representing a total amount of money.

Return the fewest number of coins needed to make up the given amount.
If it is not possible, return -1.

You may use unlimited coins of each denomination.

Example 1

Input:  coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2

Input:  coins = [2], amount = 3
Output: -1

使用 动态规划 ：
dp[x] = min(dp[x], dp[x - coin] + 1)。
初始化 dp[0] = 0、其他为无限大，最终看 dp[amount] 是否可达。

VOprep 团队长期陪同学员实战各类大厂 OA 与 VO，包括 Google、Amazon、Citadel、SIG 等，提供实时答案助攻、远程陪练与面试节奏提醒，帮助大家在关键时刻不卡壳。
如果你也在准备公司，可以了解一下我们的定制助攻方案——从编程面到系统设计，全程护航上岸。