动态规划与贪心算法的比较

192 阅读 0 评论 127 点赞

我是靠谱客的博主无私康乃馨，这篇文章主要介绍动态规划与贪心算法的比较，现在分享给大家，希望可以做个参考。

相同点：
都具有最优子结构性质。
不同点：
贪心算法具有贪心选择性质；
动态规划算法具有子问题重叠性，子问题空间小；
动态规划算法通常以自底向上的方式解各子问题；
贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。
可用贪心算法时，动态规划方法可能不适用；
可用动态规划方法时，贪心算法可能不适用。