参考答案
内容深度:适中 · 无代码示例 · 来源:外部链接 · 未复核 · 65 天前更新 · 技术内容可能随版本变化,建议结合官方文档理解
核心答案:先看『是否要枚举多种取舍求最优』与『子问题是否重叠』,再决定 DP;局部最优能递推全局且无需回头改 → 贪心;需要尝试所有路径且子问题不重叠 → 回溯。
要点(决策框架):
- 选 DP:问题要求『最大/最小/方案数』且存在重叠子问题 + 最优子结构,且决策有后效性(当前选择影响后续)。典型:背包、最长子序列、编辑距离、股票系列。
- 选贪心:能证明『每步取局部最优必达全局最优』(如活动选择、霍夫曼编码、部分区间调度);一旦不满足无后效性,贪心会错。
- 选回溯/DFS+记忆化:状态空间可枚举、子问题重叠但更自然写成递归(如全排列、子集),记忆化即 DP 的前身。
要点(反例警示):
- 0/1 背包不能贪心(按价值密度选会漏解)→ 必须用 DP。
- 求『所有路径』不是 DP 的强项,更像回溯;DP 擅长『计数/最值』而非枚举全部。
实战:先定义状态与转移试写,若发现子问题大量重复 → 上记忆化/填表;若能剪枝且状态少 → 回溯也可。