找到给定金额所需的最少硬币数量。

Find the minimum number of coins needed for change.

题目类型: 技术面试题

这是一道技术面试题，常见于澳洲IT公司面试中。

难度: medium

标签: google, real-question, igotanoffer

目标公司: Google

参考答案摘要

题目来源 IGotAnOffer 报告，Google SWE Onsite。对应 LeetCode 322 (Coin Change)，Medium。 思路分析 经典 DP 问题。dp[i] 表示凑齐金额 i 所需的最少硬币数。 解题方法 自底向上 DP 初始化 dp[0]=0，其余为 ∞。对每个金额 i，遍历所有硬币面值 coin，dp[i] = min(dp[i], dp[i-coin]+1)...

本题提供 STAR 原则详细解答和技术解析，登录匠人学院学习中心即可查看完整答案。