面试题库 › C++ / 后端 › 动态规划与贪心算法的区别

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

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

哪些公司问过

腾讯1科大讯飞1

常见岗位:计算机视觉、C++ 后端

答案要点

  1. 共同点:都依赖最优子结构
  2. 动态规划:利用重叠子问题,定义状态与转移方程,保存子问题解,自底向上或记忆化
  3. 贪心:依赖贪心选择性质,每步取局部最优且不回溯
  4. 贪心高效简单但需证明正确性,如区间调度可用、部分面额硬币找零会失败
  5. DP 时间复杂度约为状态数乘转移代价,如 0-1 背包为物品数乘容量

易错点

面试官常见追问

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

相关面试题