动态规划、贪心算法区别
本文整理自MIT算法导论公开课
动态规划是一种设计技巧，而不是一种特定的算法，就像分治法一样。
有两个序列，序列x[1 m]，序列y[1 n]，找到它们的最长公共子序列，子序列不需要在原序列中占用连续的位置（最长公共子串要求连续），子序列可能不唯一。
在最长公共子序列问题中，可以发现在递归树中有很多相同的子问题，可分析得独立子问题得数量为m·n。
世界上最重要的算法之一，在分布式系统中体现的价值尤为重要。
问题描述：输入的数据化为一个连通的无向图G=(V,E)和一个用于给每一条边加上一个实数权值的加权函数w(为了简化描述，下面的分析过程基于边的权值都不同的假设)，输出的结果为一个生成树T，并且它具有最小的权值和。
贪心算法特性：
贪心算法的关键不在于想到，而在于正确性的证明。要证明一个贪心算法是正确的，需要证明我们可以把一个最优解逐步转化为我们用贪心算法所得到的解，而解不会更差，从而证明贪心算法得到的解和最优解是一样好的（显然，最优解不可能更好)。而要证明一个贪心算法是错误的，只需要找到一个反例就可以了。
动态规划和贪心算法都是一种递推算法
均有局部最优解来推导全局最优解
贪心算法：
动态规划算法：
贪心算法与动态规划
每次拿能拿的最大的，就是贪心。
但是一定注意，贪心得到的并不是最优解，也就是说用贪心不一定是拿的最少的张数
贪心只能得到一个比较好的解，而且贪心算法很好想得到。
再注意，为什么我们的钱可以用贪心呢？因为我们国家的钱的大小设计，正好可以使得贪心算法算出来的是最优解（一般是个国家的钱币都应该这么设计）。如果设计成别的样子情况就不同了
比如某国的钱币分为 1元3元4元
如果要拿6元钱 怎么拿？贪心的话 先拿4 再拿两个1 一共3张钱
实际最优呢？ 两张3元就够了
求最优解的问题，从根本上说是一种对解空间的遍历。最直接的暴力分析容易得到，最优解的解空间通常都是以指数阶增长，因此暴力穷举都是不可行的。
最优解问题大部分都可以拆分成一个个的子问题，把解空间的遍历视作对子问题树的遍历，则以某种形式对树整个的遍历一遍就可以求出最优解，如上面的分析，这是不可行的。
贪心和动态规划本质上是对子问题树的一种修剪。两种算法要求问题都具有的一个性质就是“子问题最优性”。即，组成最优解的每一个子问题的解，对于这个子问题本身肯定也是最优的。如果以自顶向下的方向看问题树（原问题作根），则，我们每次只需要向下遍历代表最优解的子树就可以保证会得到整体的最优解。形象一点说，可以简单的用一个值（最优值）代表整个子树，而不用去求出这个子树所可能代表的所有值。
动态规划方法代表了这一类问题的一般解法。我们自底向上（从叶子向根）构造子问题的解，对每一个子树的根，求出下面每一个叶子的值，并且以其中的最优值作为自身的值，其它的值舍弃。动态规划的代价就取决于可选择的数目（树的叉数）和子问题的的数目（树的节点数，或者是树的高度？）。
贪心算法是动态规划方法的一个特例。贪心特在，可以证明，每一个子树的根的值不取决于下面叶子的值，而只取决于当前问题的状况。换句话说，不需要知道一个节点所有子树的情况，就可以求出这个节点的值。通常这个值都是对于当前的问题情况下，显而易见的“最优”情况。因此用“贪心”来描述这个算法的本质。由于贪心算法的这个特性，它对解空间树的遍历不需要自底向上，而只需要自根开始，选择最优的路，一直走到底就可以了。这样，与动态规划相比，它的代价只取决于子问题的数目，而选择数目总为1。
