面试题库 › C++ / 后端 › 零钱兑换:最少硬币数与组合数

零钱兑换:最少硬币数与组合数

难度 ★★☆在 12 场真实面经中被问到 方向:C++ / 后端考点:动态规划

哪些公司问过

字节跳动3小米1快手1京东1拼多多1阿里巴巴1网易1B站1文远知行1米哈游1

常见岗位:Java 后端、Go 后端、C/C++ 软件开发、机器学习算法(泛)、大模型算法

答案要点

  1. 面额 1、2、5 时贪心有效:优先用大面额
  2. 一般面额贪心不一定最优,如 1、3、4 凑 6,要用动态规划
  3. dp[i] 表示凑成金额 i 的最少硬币数,dp[0]=0,其余为无穷大
  4. 转移:dp[i] = min(dp[i], dp[i-coin] + 1),时间 O(金额×硬币种数)
  5. 求组合数:dp[i] += dp[i-coin],外层遍历硬币,避免把排列重复计算

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题