面试题库 › 算法 / 大模型 › 贪心算法与动态规划的区别

贪心算法与动态规划的区别

难度 ★★☆在 4 场真实面经中被问到 方向:算法 / 大模型考点:动态规划

哪些公司问过

阿里巴巴2百度1万孚生物1

常见岗位:人工智能、推理部署与加速、NLP / 语音、C/C++ 软件开发

答案要点

  1. 相同点:都依赖最优子结构,用子问题最优解构造整体解
  2. 贪心每步取局部最优且不回溯,需满足贪心选择性质才能保证全局最优
  3. 动态规划枚举所有选择并保存子问题解,利用重叠子问题避免重复计算
  4. 贪心更快更省空间,动态规划更通用但时间空间开销更大
  5. 找零问题:标准面额贪心可行,面额为 1、3、4 时贪心失败需用动态规划

易错点

面试官常见追问

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

相关面试题