分治法，动态规划法，贪心算法这三者之间有类似之处，比如都需要将问题划分为一个个子问题，然后通过解决这些子问题来解决最终问题。但其实这三者之间的区别还是蛮大的。
1.分治法
分治法（divide-and-conquer）：将原问题划分成n个规模较小而结构与原问题相似的子问题；递归地解决这些子问题，然后再合并其结果，就得到原问题的解。
分治模式在每一层递归上都有三个步骤：
-
分解（Divide）：将原问题分解成一系列子问题；
-
解决（conquer）：递归地解各个子问题。若子问题足够小，则直接求解；
-
合并（Combine）：将子问题的结果合并成原问题的解。
合并排序（merge sort）是一个典型分治法的例子。其对应的直观的操作如下：
-
分解：将n个元素分成各含n/2个元素的子序列；
-
解决：用合并排序法对两个子序列递归地排序；
-
合并：合并两个已排序的子序列以得到排序结果。
2. 动态规划法
动态规划算法的设计可以分为如下4个步骤：
-
描述最优解的结构
-
递归定义最优解的值
-
按自底向上的方式计算最优解的值
-
由计算出的结果构造一个最优解
分治法是指将问题划分成一些独立地子问题，递归地求解各子问题，然后合并子问题的解而得到原问题的解。与此不同，动态规划适用于子问题独立且重叠的情况，也就是各子问题包含公共的子子问题。在这种情况下，若用分治法则会做许多不必要的工作，即重复地求解公共的子问题。动态规划算法对每个子子问题只求解一次，将其结果保存在一张表中，从而避免每次遇到各个子问题时重新计算答案。
适合采用动态规划方法的最优化问题中的两个要素：最优子结构和重叠子问题。
最优子结构：如果问题的一个最优解中包含了子问题的最优解，则该问题具有最优子结构。
重叠子问题：适用于动态规划求解的最优化问题必须具有的第二个要素是子问题的空间要很小，也就是用来求解原问题的递归算法课反复地解同样的子问题，而不是总在产生新的子问题。对两个子问题来说，如果它们确实是相同的子问题，只是作为不同问题的子问题出现的话，则它们是重叠的。
“分治法：各子问题独立 动态规划：各子问题重叠”
https://my.oschina.net/feistel/blog/1633592
算法导论： 动态规划要求其子问题既要独立又要重叠，这看上去似乎有些奇怪。虽然这两点要求听起来可能矛盾的，但它们描述了两种不同的概念，而不是同一个问题的两个方面。如果同一个问题的两个子问题不共享资源，则它们就是独立的。对两个子问题俩说，如果它们确实是相同的子问题，只是作为不同问题的子问题出现的话，是重叠的，则它们是重叠的。
递归算法就是通过解决同一问题的一个或多个更小的实例来最终解决一个大问题的算法。为了在C语言中实现递归算法，常常使用递归函数，也就是说能调用自身的函数。递归程序的基本特征：它调用自身（参数的值更小），具有终止条件，可以直接计算其结果。
在使用递归程序时，我们需要考虑编程环境必须能够保持一个其大小与递归深度成正比例的下推栈。对于大型问题，这个栈需要的空间可能妨碍我们使用递归的方法。
一个递归模型为分治法，最本质的特征就是：把一个问题分解成独立的子问题。如果子问题并不独立，问题就会复杂的多，主要原因是即使是这种最简单算法的直接递归实现，也可能需要难以想象的时间，使用动态规划技术就可以避免这个缺陷。
例如，斐波那契数列的递归实现如下：
int F(int i)
{
if(i < 1) return 0;
if(i == 1) return 1;
return F(i-1) + F(i - 2);
}
千万不要使用这样的程序，因为它的效率极低，需要指数级时间。相比之下，如果首先计算前N个斐波那契数，并把它们存储在一个数组中，就可以使用线性时间(与N成正比)计算F。
F[0] = 0;F[1] = 1;
for(i = 2; i <= N; i++)
F[i] = F[i-1] + F[i-2];
这个技术给了我们一个获取任何递归关系数值解的快速方法，在斐波那契数的例子中，我们甚至可以舍弃数组，只需要保存前两个值。
由上面的讨论我们可以得出这样的结论：我们可以按照从最小开始的顺序计算所有函数值来求任何类似函数的值，在每一步使用先前已经计算出的值来计算当前值，我们称这项技术为自底向上的动态规划。只要有存储已经计算出的值的空间，就能把这项技术应用到任何递归计算中，就能把算法从指数级运行时间向线性运行时间改进。
自顶向下的动态规划甚至是一个更简单的技术，这项技术允许我们执行函数的代价与自底向上的动态规划一样(或更小)，但是它的计算是自动的。我们实现递归程序来存储它所计算的每一个值(正如它最末的步骤)，并通过检查所存储的值，来避免重新计算它们的任何项(正如它最初的步骤)。这种方法有时也称作为备忘录法。
斐波那契数（动态规划）
通过把所计算的值存储在递归过程的外部数组中，明确地避免重复计算。这一程序计算的时间与N成正比。
int F(int i)
{
if(knownF[i] != unknown)
return knownF[i];
if(i == 0) t = 0;
if(i == 1) t = 1;
if(i > 1) t = F(i - 1) + F(i - 2);
return knownF[i] = t;
}
性质：动态规划降低了递归函数的运行时间，也就是减少了计算所有小于或等于给定参数的递归调用所要求的时间，其中处理一次递归调用的时间为常量。
我们不需要把递归参数限制到单整形参数的情况。当有一个带有多个整形参数的函数时，可以把较小子问题的解存储在多维数组中，一个参数对应数组的一维。其他那些完全不涉及整形参数的情形，就使用抽象的离散问题公式，它能让我们把问题分解为一个个的小问题。
在自顶向下的动态规划中，我们存储已知的值；在自底向上的动态规划中，我们预先计算这些值。我们常常选择自顶向下的动态规划而不选自底向上动态规划，其原因如下：
1 自顶向下的动态规划是一个自然的求解问题的机械转化。
2 计算子问题的顺序能自己处理。
3 我们可能不需要计算所有子问题的解。
我们不能忽视至关重要的一点是，当我们需要的可能的函数值的数目太大以至于不能存储（自顶向下）或预先计算（自底向上）所有值时，动态规划就会变得低效。自顶向下动态规划确实是开发高效的递归算法实现的基本技术，这类算法应纳入任何从事算法设计与实现所需的工具箱。
3. 贪心算法
对许多最优化问题来说，采用动态规划方法来决定最佳选择有点“杀鸡用牛刀”了，只要采用另一些更简单有效的算法就行了。贪心算法是使所做的选择看起来都是当前最佳的，期望通过所做的局部最优选择来产生出一个全局最优解。贪心算法对大多数优化问题来说能产生最优解，但也不一定总是这样的。
贪心算法只需考虑一个选择（亦即，贪心的选择）；在做贪心选择时，子问题之一必须是空的，因此只留下一个非空子问题。
贪心算法与动态规划与很多相似之处。特别地，贪心算法适用的问题也是最优子结构。贪心算法与动态规划有一个显著的区别，就是贪心算法中，是以自顶向下的方式使用最优子结构的。贪心算法会先做选择，在当时看起来是最优的选择，然后再求解一个结果子问题，而不是先寻找子问题的最优解，然后再做选择。
贪心算法是通过做一系列的选择来给出某一问题的最优解。对算法中的每一个决策点，做一个当时看起来是最佳的选择。这一点是贪心算法不同于动态规划之处。在动态规划中，每一步都要做出选择，但是这些选择依赖于子问题的解。因此，解动态规划问题一般是自底向上，从小子问题处理至大子问题。贪心算法所做的当前选择可能要依赖于已经做出的所有选择，但不依赖于有待于做出的选择或子问题的解。因此，贪心算法通常是自顶向下地做出贪心选择，不断地将给定的问题实例归约为更小的问题。贪心算法划分子问题的结果，通常是仅存在一个非空的子问题。
https://juejin.im/post/5d859087f265da03bd055832
原文：http://hxrs.iteye.com/blog/1055478
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
