Question

贪心算法 动态规划 它们有什么区别？程序设计

贪心算法每一步都做目前最好的选择，不考虑下一步的选择。

动态规划的子问题每一步求的最优解影响下一个问题的最优解。

那贪心算法不就是递归的了吗？

它们只有这2点区别吗？

Answer 1

贪心算法是种策略，思想。。。
它并没有固定的模式
比如最简单的背包问题
用贪心的思想去做，就可能有很多种方法
性价比最高的、价值最高的、重量最轻的
而你没办法确保你所选择的贪心策略对所有的情况都是绝对最优的

动态规划的思想是分治+解决沉余
把一个复杂的问题分解成一块一块的小问题
每一个小问题中得到最优解
再从这些最优解中获取更优的答案
典型的例子数塔问题
画个图就能看出来

Answer 2

这个很简单啦，贪心算法是为了使得每一步都得到最好的，而最后的结果却不一定是最好的。
但是动态规划求出的肯定是最优解！！！！