正在回答
1回答
liuyubobobo
2019-11-20 13:02:32
由于通常 DP 可以解决的问题需要满足最优子结构和重叠子问题，而一个问题能贪心，不一定意味着有最优子结构或者重叠子问题，所以，更好的说法是，贪心算法能解决的，都能使用暴力搜索解决。
不过，其实，严格意义上讲，没有最优子结构和重叠子问题，也能 dp，只不过体现不出 dp 的效力而已，dp 退化成了暴力搜索。所以，说 贪心算法能解决的，也能用 dp 解决，较真地看待，也没问题。但说能贪心就一定意味着能找到最优子结构和重叠子问题，不对。
不过这种“理论”性的算法模式的区别，其实我觉得意义不大。
继续加油！：）
1
有任何疑惑可以回复我~
相似问题
第二个买草料的问题怎么感觉那么像[完全背包] 问题.
644
1
2
贪心算法？
730
0
2
即使学完课程，还是继续回来请教老师DP问题
606
0
2
关于贪心算法
491
1
1
392题和贪心算法的关系
808
0
2
登录后可查看更多问答，登录/注册
