分治算法
解决问题：
- 大整数乘法（O(n^1.59)）
- 最大值与最小值（O(3/2*n - 1)）
- 从n个元素的数组中选第k大的元素（O(n)）
动态规划
基本思路
- 把原始问题分成一系列子问题
- 求解每个子问题仅一次，并将其结果保存在一个表中，以后用到时直接存取，不重复计算
- 自底向上
操作步骤
- 分析优化解的结构
- 递归的定义最优解的代价
- 自底向上地计算最优解的代价并保存，并获取构造最优解的信息
- 根据构造最优解的信息构造优化解
解决问题
- 矩阵乘法
- 最长公共子序列问题
- 最长公共子串问题
贪心算法
基本思想
- 每一步都有一组选择
- 做出在当前看来最好的选择
- 希望通过局部优化达到全局优化
- 不一定总能产生最优解
产生优化解条件
- 贪心选择性
- 优化子结构
解决问题
- 哈夫曼编码
搜索策略
暴力搜索（适用NP问题）
深度优先和广度优先
- 广度优先实现：队列
- 深度优先实现：栈
搜索优化策略
- 爬山法
- 适用深度优先
- 用贪心法确定搜索方向
- 用启发式测度来排序节点扩展的顺序
- Best First搜索
- 根据一个评价函数，从目前产生的所有结点中选择具有最小函数评价值的节点进行扩展
- 具有全局化的观念
- 适用堆
- 分支界限
- 适用于求解最优解问题
- 发现优化解的一个界限
- 缩小解空间，提高求解的效率
字符串搜索
rabin-karp算法
KMP算法
- 自动机搜索
