贪心法和动态规划的异同

贪心法和动态规划是算法设计中两种常见且重要的策略。

一、定义与适用场景

贪心法（Greedy Algorithm）是一种简单、直观且易于设计的算法， 它在每一步选择中都采取当前状态下最好或最优（即最有利）的选择，以求全局最优解。贪心算法一般用来解决最优化问题， 如最小生成树、求最小路径、 背包问题等。

而动态规划（Dynamic Programming）是一种将各个子问题重复计算的策略，将子问题的解存储下来，再用已经求解过的子问题的解来推导更大规模的子问题的解。常用于处理带有重叠子问题和最优子结构性质的问题， 如背包问题、最长公共子序列问题、编辑距离问题等。

二、算法思想

贪心算法的思想是：从问题的某个初始解出发逐步地逼近所求解， 总是做出在当前看来最好的选择 。贪心策略不是对所有的问题都能得到全局最优解的保证，但是可以对大部分问题得到最优解，或者是次优解。

动态规划算法则是一种将原问题拆分成若干子问题，并先求解小子问题，再汇总解决整个问题的算法策略。它试图通过将原问题拆分为多个更小、更简单的子问题来解决问题， 子问题的答案被存放在一个表格中， 并被用来解决更大子问题的答案。每个子问题只被求解一次，然后存储结果，减少了重复的计算，提高了算法的效率。

三、优缺点

贪心算法的优点：

1. 贪心算法一般很快， 便于实现。

2. 对于全局最优解比较容易求解的问题，贪心算法通常是最优解法。

贪心算法的缺点：

1. 不能保证得到最优解， 即不能保证全局最优。

2. 对问题的数学证明要求很高， 不同背景知识之间的适应需要很多实践经验。

动态规划算法的优点：

1. 可以求解各种不同类型的最优化问题， 即可以处理多种不同的最短路径和最优解等问题。

2. 程序写起来相对复杂， 但运行效率高且稳定。

动态规划算法的缺点：

1. 需要大量的额外空间来存储所有的子问题的答案表格。

2. 如果问题中存在多个局部最优解， 动态规划算法很难处理。

四、应用实例

贪心算法常见应用：

1. 最小生成树问题： Kruskal、 Prim算法；

2. 路径规划问题： Dijstra算法；

3. 背包问题： 分数背包问题。

动态规划算法经典应用：

1. 最长公共子序列问题；

2. 区间规划；

3. 背包问题。

五、相应算法复杂度

在一些问题中，动态规划算法比贪心算法更加高效，也就是说， 一些问题贪心算法无法处理， 需要使用动规策略解决。

动态规划算法的复杂度通常为指数级别（需要遍历所有可能的状态），而贪心算法的复杂度则通常为线性或近似线性级别（处理每个状态的复杂度为常数）。

综上，贪心法和动态规划虽然在思想和实现上有诸多不同，但是相互补充、协作，一起构成了算法设计的重要分支。