面试题库 › C++ / 后端 › 零钱兑换 II:凑成金额的组合数(LC518)

零钱兑换 II:凑成金额的组合数(LC518)

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

哪些公司问过

京东1

常见岗位:C/C++ 软件开发

答案要点

  1. dp[j] 表示凑成金额 j 的组合数,dp[0] = 1
  2. 外层遍历硬币、内层正序遍历金额,求组合数
  3. 转移:dp[j] += dp[j - coin]
  4. 交换循环顺序得到的是排列数
  5. 时间 O(n × amount),空间 O(amount)

易错点

面试官常见追问

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

相关面试题