贰.1.6 分治法、动态规划与贪心算法的区别

分治法，动态规划、贪心算法三者之间有类似之处，比如都需要将问题划分为一个个子问题，然后通过求解子问题来得到最终解，但其实这三者之间的区别还是很大的。
01.分治法
分治法(Divide-and-Conquer) : 将原问题划分成n个规模较小而结构、且与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。
分治模式在每一层递归上都有三个步骤：
分解(Divide)：将原问题分解成一系列子问题；
解决(Conquer)：递归地解决各个子问题。若子问题足够小，则直接求解。
合并(Combine)：将子问题的结果合并成原问题的解。
​快速排序是一个典型分治法的例子。
02.动态规划
动态规划算法的设计可以分为如下4个步骤：
描述最优解的结构
递归定义最优解的值
按自底向上的方式计算最优解的值
由计算出的结果构造一个最优解
分治法是指将问题划分成一些独立的子问题，递归的求解各子问题，然后合并子问题的解而得到原问题的解。与此不同，动态规划适用于子问题独立且重叠的情况，也就是各子问题包含公共的子子问题。在这种情况下，若用分治法则会做许多不必要的工作，即重复地求解公共的子问题。动态规划算法对每个子子问题只求解一次，将其结果保存在一张表中，从而避免每次遇到各个子问题时重新计算答案。
适合采用动态规划方法的最优化问题中的两个要素：最优子机构和重叠子问题。
最优子机构：如果问题的一个最优解中包含了子问题的最优解，则该问题具有最优子机构。
重叠子问题：子问题的空间要很小，也就是用来求解原问题的递归算法反复地解同样的子问题，而不是总是在产生新的子问题。对两个子问题来说，如果它们确实是相同的子问题，只是作为不同问题的子问题出现的话，则它们是重叠的。
一句话总结分治法与动态规划的区别： 分治法 —— 各子问题独立；动态规划 —— 各子问题重叠。
引自《算法导论》：
动态规划要求其子问题既要独立又要重叠，这看上去似乎有些奇怪。虽然这两点要求听起来可能矛盾的，但它们描述了两种不同的概念，而不是同一个问题的两个方面。如果同一个问题的两个子问题不共享资源，则它们就是独立的。对两个子问题来说，如果它们确实是相同的子问题，只是作为不同问题的子问题出现的话，是重叠的，则它们是重叠。
延伸阅读（建议必读）
1) 司徒正美讲动态规划：Javascript背包问题详解​
2)【动态规划】三种背包问题（01背包、完全背包、多重背包）​
华为实战题
有一座独木桥，长度为L，青蛙每跳一次的最大距离为M，最小距离为S，桥上有N个石墩，石墩不会落在两端只在桥中间，桥墩位置数组为Postions，青蛙很不喜欢站在石墩上。问：青蛙最少要几步能过桥，而且满足落在石墩上的次数最少。
举例输入：L=10,S=1,M=3,N=5,Positions=[2,4,5,7,9]
应该输出：2
//todo
03.贪心算法
对许多最优化问题来说，采用动态规划方法来决定最佳选择有点“杀鸡用牛刀”了，只要采用另一些更简单有效的算法就行了。贪心算法是使所做的选择看起来都是当前最佳的，期望通过所做的局部最优选择来产生出一个全局最优解。贪心算法对大多数优化问题来说能产生最优解，但也不一定总是这样的。
贪心算法只需考虑一个选择（亦即，贪心的选择）；在做贪心选择时，子问题之一必须是空的，因此只留下一个非空子问题。
贪心算法与动态规划与很多相似之处。特别地，贪心算法适用的问题也是最优子结构。贪心算法与动态规划有一个显著的区别，就是贪心算法中，是以自顶向下的方式使用最优子结构的。贪心算法会先做选择，这个选择在当时看起来是最优的，然后再求解一个结果子问题；而不是先寻找子问题的最优解，然后再做选择。
贪心算法是通过做一系列的选择来给出某一问题的最优解。对算法中的每一个决策点，做一个当时看起来是最佳的选择。这一点是贪心算法不同于动态规划之处。在动态规划中，每一步都要做出选择，但是这些选择依赖于子问题的解。因此，解动态规划问题一般是自底向上，从小子问题处理至大子问题。贪心算法所做的当前选择可能要依赖于已经做出的所有选择，但不依赖于有待于做出的选择或子问题的解。
因此，贪心算法通常是自顶向下地做出贪心选择，不断地将给定的问题实例归约为更小的问题。贪心算法划分子问题的结果，通常是仅存在一个非空的子问题。

贰、数据结构与算法 - 以前

贰.1.5 实战：字节跳动前端面试2道算法题

下一个 - 贰、数据结构与算法

贰.1.7 实战：阿里巴巴前端面试题

最近更新 2yr ago

复制链接

大纲

01.分治法

02.动态规划