请解决零钱兑换问题：给定不同面额的硬币 coins 和一个总金额 amount，编写一个函数来计算可以凑成总金额所需的最少硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
考察说明
考察动态规划状态定义、转移方程及边界处理
回答思路
- 正确理解问题并说明动态规划适用性
- 定义 dp[i] 表示凑成金额 i 所需的最少硬币数
- 写出转移方程 dp[i] = min(dp[i], dp[i-coin]+1) 并处理子问题无解情况
- 能正确初始化 dp[0]=0 和其余为无穷大
- 给出解法的时间与空间复杂度，并能解释为什么贪心不一定正确
本题已收录答题指导
本题附完整参考答案与评分标准
登录后可查看结构化答题指导；也可以直接开一场模拟面试，AI 面试官用本题实时追问并给出评分。