最近一位学员在 Amazon 的线上技术面试中遇到一道非常典型的动态规划题——看似简单，却能在十几分钟内迅速区分出“只会写代码的人”和“理解算法本质的人”。

🧩 英文原题如下：

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）+ 边界初始化。

候选人先尝试了暴力回溯思路（递归枚举所有组合），但在第二个测试样例时超时。
随后我们协助学员快速转化为自底向上的 DP 解法

在调试时，我们重点强调：

• 初始化错误 是最常见的陷阱（dp 数组默认值不可用 0）。
• 返回边界条件 必须正确识别“无法组成的情况”。
• 面试沟通逻辑：讲清楚递推关系 “dp[i] = min(dp[i - coin] + 1)”。

面试官对答题思路与讲解逻辑非常满意，甚至表示“这就是理想的 Amazon 面试风格答案

➡️ 可以联系 CSOAHelp（我们提供高质量 OA/VO 面试辅助与全流程解析）。