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

联系

分治、动态规划、贪心算法都是把一个大的问题给分解成子问题，通过解决子问题来最终解决原问题的。

区别

分治： 子问题不重复时候更适合，重复也能用，效率低，最好动态规划。
动态规划： 重复的公共子问题和最优子结构，记录已经计算过的子问题，用空间换时间。在动态规划中，每一步都要做出选择，但是这些选择依赖于子问题的解
贪心： 能用贪心解决的都能用动态规划解决，自顶向下，不等所有子问题求解完毕再选择使用哪一个的解，而是直接人为的通过一种策略选择一个子问题去求解。
回溯： 深度搜索+剪枝思想，能用贪心 动态解决的都能用回溯解决

分治

大部分分治也是求子问题的最优解，不过也有不是的。

算法步骤：
分解（Divide）：将原问题分解成一系列子问题；
解决（conquer）：递归地解各个子问题。若子问题足够小，则直接求解；
合并（Combine）：将子问题的结果合并成原问题的解。
重点是：写递归方程
分治法求解的经典案例有：快速排序，归并排序，二分搜索等

动态规划

算法步骤：
重点是：写转移方程
例如经典数塔问题，用自底向上的动态规划，上一层的每个结点都会从它所有子结点中选择最大的，这样依次递推，到第一层的右下和左下，各自的最大和必定为其路径的最大和。

贪心

贪婪算法并没有固定的算法解决框架，算法的关键是贪婪策略的选择，根据不同的问题选择不同的策略。

必须注意的是策略的选择必须具备无后效性，即前面选择什么对后面没影响，A B C三个字母选择两个，有后效性只能选AB AC,无后效性可以AA AB AC。

步骤：

1.明确什么是最优解
2.明确子问题的最优解策略，即选择一个策略来解决子问题
3.分别求出子问题的解堆叠成最终解

经典例题：爬楼，一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。