Data Structures and Algorithms Basics（018）：总结

上面是该系列（数据结构与算法基础）的目录结构，包含了常见的数据结构和算法，下面介绍三大算法（分治算法，动态规划，贪心算法）的核心思想及使用场景。

1，三大算法简介：

贪心算法：贪心算法采用的是逐步构造最优解的方法。在每个阶段，都在一定的标准下做出一个看上去最优的决策。决策一旦做出，就不可能再更改。做出这个局部最优决策所依照的标准称为贪心准则。

分治算法：分治法的思想是将一个难以直接解决大的问题分解成容易求解的子问题，以便各个击破、分而治之。

动态规划：将待求解的问题分解为若干个子问题，按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。

2，三大算法特点：

1）、动态规划：

依赖：依赖于有待做出的最优选择

实质：就是分治思想和解决冗余。

自底向上（每一步，根据策略得到一个更小规模的问题。最后解决最小规模的问题。得到整个问题最优解）

特征：动态规划任何一个i+1阶段都仅仅依赖 i 阶段做出的选择。而与i之前的选择无关。但是动态规划不仅求出了当前状态最优值，而且同时求出了到中间状态的最优值。

缺点：空间需求大。

2）、贪心算法：

依赖：依赖于当前已经做出的所有选择。

自顶向下（就是每一步，根据策略得到一个当前最优解。传递到下一步，从而保证每一步都是选择当前最优的。最后得到结果）。

3）、分治算法：

实质：递归求解

缺点：如果子问题不独立，需要重复求公共子问题。

3，三大算法适用条件：

贪心算法：

①贪心选择性质：在求解一个问题的过程中，如果再每一个阶段的选择都是当前状态下的最优选择，即局部最优选择，并且最终能够求得问题的整体最优解，那么说明这个问题可以通过贪心选择来求解，这时就说明此问题具有贪心选择性质。

②最优子结构性质：当一个问题的最优解包含了这个问题的子问题的最优解时，就说明该问题具有最优子结构。

动态规划：

①最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。

②无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。

③有重迭子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。

分治算法：

1）规模如果很小，则很容易解决。/一般问题都能满足

2）大问题可以分为若干规模小的相同问题。/前提

3）利用子问题的解，可以合并成该问题的解。/关键

4）分解出的各个子问题相互独立，子问题不再包含公共子问题。 /效率高低

4，优势：

采用动态规划方法，可以高效地解决许多用贪婪算法或分而治之算法无法解决的问题。

贪心算法也有它的优势：构造贪心策略不是很困难，而且贪心策略一旦经过证明成立后，它就是一种高效的算法。