Amazon OA 面试真题解析：Change Counting System（最少硬币凑零钱）

You’re creating a change counting system for a new automated Amazon cash register that Amazon plans to launch internationally.

Your change counting system should take the amount of change needed plus the types of coins available and return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:

Desired change: 6¢
Coins Available: [5¢, 3¢]
Result: 2

Example 2:

Desired change: 18¢
Coins Available: [5¢, 3¢]
Result: 4

Example 3:

Desired change: 7¢
Coins Available: [5¢, 3¢]
Result: -1

这道题本质上是经典的最少硬币凑金额问题：给定目标金额和若干面值的硬币，要求用尽可能少的硬币凑出指定金额，若无法凑出则返回 -1。通常可用动态规划来求解，dp[i] 表示凑出金额 i 所需的最少硬币数，状态转移时枚举每一种硬币面值，取“使用当前硬币一次后的最优值 + 1”的最小值。题目中的例子展示了可行解与不可行解两种情况，例如 6 可以由 3+3 凑出，18 需要 4 枚 5 和 3 组合，而 7 无法由 5 和 3 组成。