前言

最近在阅读一本有趣的算法书，书中作者列举了四种基本的算法设计模式，我总结摘录得到本文。今天先给出文字总结。随着阅读的深入，以后会给出四种设计模式的典型案例。

正文

贪婪法

- 核心思想：
    将原问题划分为多个子情况考虑，在每一个子情况中寻求其局部最优解，然后将局部最优解按照一定的方式（这种方式通常与子问题的划分方式有关）堆叠得到原问题的解。
- 特点：
    1. 这种方法不用考虑子问题之间的相互影响（这一点区别于动态规划方法），通俗的说，就是不用“瞻前顾后”。
    2. 在每个子问题中都应用了局部最优原则，寻求该子问题的最优解。
- 一般思路：
    定义最优解模型->划分子问题->定义子问题的最优解结构->确定局部最优解，并堆叠出全局最优解。

分治法

- 核心思想：
    将大问题划分为一系列子规模较小的相同问题（解结构相同，子问题之间相互独立），寻找子问题的解之后将结果合并得到原问题的解。
- 特点：
    子问题的划分不一定只有一次，而且往往不止一次，划分的目的是使每一个子问题相互独立而且是容易求解和能够最后组合得到原问题的解。正因为这个特点，分治法与递归思想总是密不可分的。
- 难点：
    子问题的划分方式和最后结果的合并。如果用递归去解决分治法问题时，难点就是寻找递归关系式和确定递归终止条件。
- 举例：N点离散傅里叶变换的快速计算

动态规划

- 核心思想：
    要解一个给定问题，我们需要解其不同部分，再合并子问题的解以得到原问题的解。
- 特点：
    1. 动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划保存递归时的结果，因而不会在解决同样的问题时花费时间。                                              
    2. 适用于无后效性的问题。子问题的解一旦确定之后就不会改变，不受之后包含它的更大的问题的求解。
    3. 适用于子问题相互重叠的情况。动态规划会创建一张“表”记录每个子问题的计算结果，当再次需要计算此问题时就可以通过查表快速得到结果，简化计算。
- 一般思路：
    定义最有子问题->定义状态->定义决策和状态转换方程式->确定边界条件。
- 举例：
    斐波那契数列的计算（在计算过程中保存每一步的f(n)）、0-1背包问题

穷举法

- 核心思想：
    在解空间之内穷举并测试每个可能的结果。
- 穷举策略：
    1. 盲目搜索算法。
    2. 启发式搜索（开始搜索时加入了一定的附加条件）
    3. 剪枝策略：跳过一些明显不会是最优解的分支的搜索。
- 应用举例：很多NP问题的求解最后都是用了枚举法。

后记

四种基本的设计模式并不是相互对立的。有时一个问题可以用一种或多种的设计模式去解决，而且，附加的条件不同时，应用的设计方法也不同。一个典型例子就是背包问题（多件体积不同，价值不同的物品放入体积一定的背包，求解价值最大的方案），既可以通过穷举所有情况解决，也可以引入价值密度的概念，用贪婪法设计解决(每次都放入价值密度最高的物品），还可以用动态规划解决（还没透彻理解QAQ）。
上面的内容很多都是自己整理书中内容加上自己的一点想法写成的，感觉还是太抽象了，也难免有各种疏漏和错误，欢迎大家留意指正，多多交流。以后补充实际问题结合代码更加深入的分析每一个方法的奥妙。