Question

大学课程《算法分析与设计》中动态规划和贪心算法的区别和联系？

Answer 1

对于，大学课程《算法分析与设计》中动态规划和贪心算法的区别和联系这个问题，首先要来聊聊他们的联系：1、都是一种推导算法；2、将它们分解为子问题求解，它们都需要有最优子结构。这两个特征师门的联系。

然后，下面来说说他们的差别：贪心算法需要每一步的最优解必须包含前一步的最优解，前一步的最优解不保留；而动态规划是全局最优解必须包含一个局部最优解，而不是先前的局部最优解。因此，有必要记录所有以前的局部最优解。

另一个不同是，贪心算法它如果所有子问题都被视为一棵树，贪婪从根开始，每次都遍历最优子树（通常这种“最优”基于当前情况下明显的“最优”）；这样，就不需要知道一个节点的所有子树，所以它不能形成一个完整的树；而动态规划是从下到上，从叶到根构造子问题的解决方案。对于每个子树的根，找到下面每个叶子的值。最后，得到一棵完整的树，最后选择最优值作为自己的值来得到答案。

可见，根据以上描述，贪心算法不能保证最终的解决方案是最好的，总体复杂度较低；动态规划的本质是穷举法，它能保证最优的结果和较高的复杂性。特别是对于0-1背包问题，它应该比较选择项目和不选择项目所导致的最终方案，然后做出最佳选择。由此衍生出许多重叠子问题，因此使用了动态规划。

拓展资料：

贪婪算法是指在解决问题时，它总是在当前做出最佳选择。也就是说，在不考虑全局优化的情况下，该算法在某种意义上获得了局部最优解。贪婪算法不能得到所有问题的全局最优解。关键是贪婪策略的选择。

动态规划是运筹学的一个分支，是解决决策过程优化的过程。20世纪50年代初，美国数学家R·贝尔曼等人在研究多阶段决策过程的最优化问题时，提出了著名的最优化原理，建立了动态规划。动态规划在工程技术、经济、工业生产、军事和自动控制等领域有着广泛的应用，在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题上都取得了显著的成果。