分治算法 贪心算法 动态规划 区别

分治算法、贪心算法和动态规划算法是三种常见的算法思想。它们有一些共性，但也有一些区别。

1. 分治算法

分治算法是将原问题划分为若干个子问题，递归地求解每个子问题，最后将子问题的解合并起来，得到原问题的解。分治算法通常可以用递归实现。典型的例子包括归并排序和快速排序。

2. 贪心算法

贪心算法是一种简单而有效的算法思想，它总是在当前状态下做出局部最优的选择，希望最终能够得到全局最优解。贪心算法通常需要证明贪心选择性质和最优子结构性质，以保证其正确性。典型的例子包括霍夫曼编码和最小生成树算法。

3. 动态规划

动态规划是一种将原问题划分为若干个子问题，递归地求解每个子问题，最后将子问题的解合并起来，得到原问题的解的算法思想。与分治算法类似，但是它通常需要用一个表格来存储子问题的解，以避免重复计算。动态规划算法通常需要证明最优子结构性质和无后效性质，以保证其正确性。典型的例子包括背包问题和最长公共子序列问题。

总之，三种算法思想都是通过将问题划分为若干个子问题来求解原问题，但是它们的具体实现方式不同，适用的场景也不同。