Algorithms
动态规划 Dynamic Programming
要解一个给定的问题，只需要解其不同的部分(子问题),再跟据子问题的解得到原问题的解。 通常许多子问题非常相似，因此动态规划试图仅仅解决每个子问题一次，从而减少计算量： 一旦一个给定的子问题已经解出，就将其存储，以便下次需要同一个子问题的解时直接查表。
减治法 Decrease-and-conquer
利用了一个问题给定的实例的解和同样问题较小实例的解之间的关系。一旦建立了这种关系， 我们既可以自顶向下(往往是递归)，亦可从底至上(迭代)地来运用该关系。
自底至上的版本往往时迭代实现的，从解决问题的一个较小的实例开始，该方法有时也 称为 增量法(Incremental Approach)
减治法由三种主要变化形式：
- 减去一个常量
- 减去一个常量因子
- 减去的规模时可变的
分治法 Divide-and-conquer
顾名思义，分而治之：将无法解决的大问题分解成一系列规模的较小的相同问题， 然后逐个解决小的问题，即所谓的分而治之。分治法产生的子问题与原始问题相同， 只是规模减小，反复使用分治法，可以使子问题的规模不断减小，直到能够被直接求解。
分治法基本上可以归纳为三个步骤:
- 分解: 将问题分解为若干规模较小、相互独立的且与原问题形式相同的子问题，确保每个子问题 的解都有相同的子结构。
- 解决: 如果上一步分解得到的子问题可以解决，则解决这些子问题，否则使用和上一步
- 合并: 将上一步解决的各个子问题的解通过某种规则合并起来，的到原来问题的解
变治法 Transform-and-conquer
基于变换的思想。首先把问题变得更容易求解。然后，对实例进行求解。
变治思想主要有三种类型：
- 变换为同样问题更加简单或者更加方便的实例——实例化简(instance simplification)
- 变换为实例的不同表现——改变表现(representation change)
- 变换为另一个问题的实例，这种问题的算法是已知的——问题化简(problem reduction)
贪婪法 Greedy algorithm
一般把求解过程分成若干步骤，每个步骤都应用贪心原则， 选取当前状态下最好或者 最优的解（局部最有利的选择），并希望最后堆叠出的结果也是最优解。
一般来说，这种贪心原则在各种算法模式中都有所体现，单独作为一种方法来说明， 是因为对于特定的问题是非常有效性的方法。
贪婪法的基本思想有以下三个步骤：
- 建立一个对问题精确描述的数学模型，包括最优解的模型；
- 将问题分解为一系列的子问题，同时定义子问题的最优解结构；
- 应用贪心原则确定每个子问题的局部最优解，并根据最优解的模型，用子问题的局部 最优解堆叠出全局最优解。