贪心算法和动态规划算法共有特点是

2025-02-23 12:14:43

推荐回答（2个）

回答1：

都是求最优解，
其实这么问真的不好，因为他们在本质上有很大差别，
贪心是每次求局部最优，最后得到全局最优，当然，要保证局部最优能够得到全局最优
而动规则是把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，其实每一步都枚举了所有的情况，类似于分治，也可以说类似于搜索（只不过状态出现后就被记录了，这就是记忆化搜索，或者用填表的方式）。

回答2：

贪心是特殊的动规。所谓特殊，是因为状态的转移时O(1)的。
动规转移的过程是贪心地进行的。每次选择所有前驱状态的最优值来更新当前状态的值。
动规与贪心有联系又有区别，其中最大的区别就是是否有后效性。
很少有人真正能讲清后效性是什么，平常做题目时，最简单的区分方法是判断贪心是否是对的，如果是对的，说明它没有后效性，否则就有后效性。