bobo老师，对于动态规划和贪心算法的区别我不是很清楚呀？也不知道什么适合使用贪心算法？bobo老师有时间可以解答一下吗？
来源：6-5 BFS和图的最短路径 Perfect Squares
慕九州3352676
2019-02-01
输入正文
1回答
-
首先，动态规划和贪心的区别还是很明显的。贪心是使用一个单一的方法前进，而动态规划则是尝试所有的可能，只不过中间使用“表格”进行记忆（所以要满足重叠子问题和最优子结构的性质）。01背包问题是最好的例子。每次都放剩下的物品中单位价值最高的物品，是贪心（单一的策略前进）；而动态规划其实每次尝试了拿去所有的物品。（01背包问题在课程中有详细介绍，可以再仔细回顾体会一下。）
但具体什么时候可以使用贪心算法？这是一个很大的问题了。甚至，很多时候，证明一个问题的贪心算法是正确的，比写出一个贪心算法实际试验一下，看看贪心算法是否成立，都要费时费力：）
如果理论来讲，只要满足“贪心性质”的问题，就能使用贪心算法。但是问题复杂就复杂在，到底什么问题满足“贪心性质”？这个不是一概而论的，要具体问题具体分析。比如，举两个最有名的例子，在最小生成树算法中，Kruskal算法是典型的贪心算法（排序后每次取最小的不能形成环的边）；哈夫曼树的构建也是典型的贪心算法（每次选择当前频次最低的两棵子树合并构成新的树）。而实际上，证明这两个算法为什么可以使用岩心的思想，是完全没有联系的：-（
这本身也是算法复杂的地方。如果能够简单的用一个或者几个原则，就能概括出什么时候可以使用贪心，什么时候可以使用动态规划，什么时候只能回溯。。。那么，算法就太容易了，也不会让那么多人头疼了，这个世界也就不会有那么多算法比赛了。算法设计本身就具有一定的艺术成分。需要对算法的深刻理解和在遇到具体问题时敏锐的直觉：）至少，很抱歉，我没有“秘诀”，能够让你瞬间掌握什么时候可以使用贪心，什么时候需要使用动态规划。如果一定要的话，一个“应试”的方法是看数据规模。由于贪心算法的复杂度通常都会很低（O(n)或O(nlogn)），而动态规划算法通常都是O(n^2)的（但并不一定），所以，如果问题的数据规模是O(n^2)级别的算法无法承受的话，通常可以想想是否可以贪心：）
不过这是很“应试“的方法，如果真要彻底掌握这二者，相信我，绝不是容易的事情。即使很多高级别的比赛选手，也会在这两个算法问题中栽跟头。我的建议是，大量的见不同的问题。Leetcode上无论是动态规划的问题，还是贪心问题，都很多，按照标签一个一个刷。每个问题都思考一下，动态规划的问题可不可以贪心？贪心的问题可不可以动态规划？为什么可以或者为什么不可以？大量的见识更多的算法问题，自己不断的整理总结思考，最终就会慢慢形成自己解决问题的思路和直觉：）
关于更多学习方法方面的建议，可以参考我的公号文章：《高效学习的秘密》：）
加油！：）
212019-02-01
相似问题
回答 1
回答 1