Question

动态规划和贪心算法的区别

Answer 1

如下：

贪心法是每一步的最优解就是整体的最优解。0-1背包是属于动态规划，每一步的解不一定导致整体的最优解。

对于你问“什么样的题用0-1背包问题作”就是需要你自己做题来体会了。如果全局的最优解可以用分布的最优解求出来，就用贪心，如果不是，就动态规划（0-1背包属于这类）。

合并果子问题（可以自己去网上找哈~）就是典型的贪心，0-1背包问题就属于典型动态规划。

贪心算法特性：

贪心算法的关键不在于想到，而在于正确性的证明。要证明一个贪心算法是正确的，需要证明我们可以把一个最优解逐步转化为我们用贪心算法所得到的解。

而解不会更差，从而证明贪心算法得到的解和最优解是一样好的（显然，最优解不可能更好)。而要证明一个贪心算法是错误的，只需要找到一个反例就可以了。

动态规划和贪心算法都是一种递推算法，
均有局部最优解来推导全局最优解，

贪心算法：

动态规划算法：

贪心算法与动态规划。

每次拿能拿的最大的，就是贪心。

但是一定注意，贪心得到的并不是最优解，也就是说用贪心不一定是拿的最少的张数。