共同点：
都需要最优子结构性质，
都用来求有优化问题。
不同点：
动态规划：每一步作一个选择—依赖于子问题的解。
贪心方法：每一步作一个选择—不依赖于子问题的解。
动态规划方法的条件：子问题的重叠性质。
可用贪心方法的条件：最优子结构性质；贪心选择性质。
动态规划：自底向上求解；
贪心方法：自顶向下求解。
可用贪心法时，动态规划方法可能不适用；
可用动态规划方法时，贪心法可能不适用。
（简答题）
请叙述动态规划算法与贪心算法的异同。
正确答案
答案解析
略
相似试题
（单选题）
贪心算法与动态规划算法的主要区别是（）。
（单选题）
（）是贪心算法与动态规划算法的共同点。
（填空题）
（）是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
（单选题）
一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（）。
（填空题）
问题的（）是该问题可用动态规划算法或贪心算法求解的关键特征。
（简答题）
算法设计中的分治策略、贪心策略、动态规划策略、回溯策略以及分支定界策略的基本思想是什么？
（简答题）
对下图所示的连通网络G，用克鲁斯卡尔（Kruskal）算法求G的最小生成树T，请写出在算法执行过程中，依次加入T的边集TE中的边。说明该算法的贪心策略和算法的基本思想，并简要分析算法的时间复杂度。
（填空题）
贪心算法算法的基本要素是（）、（）。
（简答题）
简述动态规划算法的基本步骤。
