网友评论得挺实在：“可以联系HR问问看能不能恢复。”对啊，哪怕希望渺茫，也得试试。讲道理，有些公司还是讲人情的，尤其这种技术岗位，招人本来也不容易。
算法题：零钱兑换
问题描述
coins，里面是各种面值的硬币，比如 [1, 2, 5]，然后还有一个整数 amount，表示目标金额。你的任务是计算用这些硬币拼出目标金额所需的最少硬币数。如果没法拼出来，那就返回 -1。Input: coins = [1, 2, 5], amount = 11
Output: 3 // 11 = 5 + 5 + 1
动态规划的套路
dp，dp[i] 表示拼出金额 i 所需的最少硬币数。那么：dp[0] = 0，因为金额为0时不需要硬币。如果金额为 i，我们可以从每个硬币coin开始试，比如尝试从金额i - coin加一个硬币，看哪个结果最优。
dp[i] = Math.min(dp[i], dp[i - coin] + 1)
代码实现
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
// 初始化为最大值，表示暂时无法拼出
Arrays.fill(dp, amount + 1);
dp[0] = 0; // 金额为0时需要0枚硬币
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (i - coin >= 0) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
代码解析
外层循环：遍历每一个金额 i，从 1 到amount。内层循环：尝试每个硬币面值 coin，看看用它拼金额i的方案能不能更优。初始化和判断：用 amount + 1作为初始值，因为这是不可能达到的硬币数量，便于后续找最小值。
dp[amount] 就是拼出目标金额的最优解。如果 dp[amount] 还是初始值，那说明压根拼不出来，返回 -1。性能优化
O(amount * n)，其中 n 是硬币种类数量。这已经是比较合理的性能了，不过面试官可能会问你能不能优化到更快。这时候可以偷摸反问一句：“这题允许使用量子计算吗？” 😂小坑提醒
硬币值无序：题目没要求硬币数组是有序的，所以别偷懒假设 [1, 2, 5]一定是升序。大金额：测试用例可能会给你一个非常大的 amount，比如 10000。所以初始化时别忘了用一个足够大的值，比如amount + 1，而不是Integer.MAX_VALUE，后者可能溢出。
-END-
以上，就是今天的分享了，看完文章记得右下角给何老师点赞，也欢迎在评论区写下你的留言。
