面试题库 › 嵌入式 › 接待车坐满方案数(背包计数)

接待车坐满方案数(背包计数)

难度 ★★☆在 1 场真实面经中被问到 方向:嵌入式考点:动态规划

哪些公司问过

华为1

常见岗位:软件开发(未写技术栈)

答案要点

  1. 问题转化为子集和等于容量的方案数,每个代表团最多选一次
  2. dp[j] 表示人数和恰为 j 的方案数,dp[0] = 1
  3. 内层容量倒序遍历,转移 dp[j] += dp[j - w]
  4. 答案为 dp[容量],无解时为 0
  5. 时间 O(n × C),空间 O(C)

易错点

面试官常见追问

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

相关面试题