IT 面试题库

拿到一道算法题,你如何判断该用「动态规划」还是「贪心 / 回溯」?给出决策框架与反例。

高级开放题算法工程师动态规划贪心回溯算法选型

题目

考察点:算法选型思维——从问题结构(最优子结构、后效性、是否需枚举)判断解法,而非套模板(高级开放题)。

参考答案

内容深度:适中 · 无代码示例 · 来源:外部链接 · 未复核 · 65 天前更新 · 技术内容可能随版本变化,建议结合官方文档理解

核心答案:先看『是否要枚举多种取舍求最优』与『子问题是否重叠』,再决定 DP;局部最优能递推全局且无需回头改 → 贪心;需要尝试所有路径且子问题不重叠 → 回溯。

要点(决策框架):

要点(反例警示):

实战:先定义状态与转移试写,若发现子问题大量重复 → 上记忆化/填表;若能剪枝且状态少 → 回溯也可。

练这道题

同分类 · 高频题

题目与答案就在本页;收藏、批注和错题重练在应用内

这道题看完了?连刷同类题,趁热打铁效果最好 进入刷题