贪心和DP

来源：10-2 贪心算法与动态规划的关系 Non-overlapping Intervals

程序员不会说方言

2019-11-20

bobo老师你好，我想问下：是否所有可以用贪心算法解决的，DP都可以解决呢？

写回答

1回答

liuyubobobo

2019-11-20

已采纳

由于通常 DP 可以解决的问题需要满足最优子结构和重叠子问题，而一个问题能贪心，不一定意味着有最优子结构或者重叠子问题，所以，更好的说法是，贪心算法能解决的，都能使用暴力搜索解决。

不过，其实，严格意义上讲，没有最优子结构和重叠子问题，也能 dp，只不过体现不出 dp 的效力而已，dp 退化成了暴力搜索。所以，说贪心算法能解决的，也能用 dp 解决，较真地看待，也没问题。但说能贪心就一定意味着能找到最优子结构和重叠子问题，不对。

不过这种“理论”性的算法模式的区别，其实我觉得意义不大。

继续加油！：）

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题，高频算法题解析，强化训练

7410 学习 · 1150 问题

相似问题

回答 1

回答 1

回答 1

回答 1

回答 1