分治算法
分而治之，将复杂的问题分成更多子问题，解决子问题，最后合并子问题的解即原问题的解。
条件:
该问题缩小后很容易解决
子问题的解可以合并为该问题的解
各个子问题是相互独立。(特征点)
步骤:
分解
解决
合并
通用模型:
FUNC(p)
if p <= n0
then return adhoc(p)
将p分解各子问题
for i->1 to k
do yi <- FUNC(pi)
T <- merge(y1,y2…yk);
return T
应用场景:
二分搜索
大整数除法
合并排序
快排
汉诺塔
循环赛日程表/棋盘覆盖
解题思维过程
类似数学的归纳法，找到解决问题的求解方程式，然后根据方程式设计递归程序
一定先找到最小问题以及求解方法
然后考虑随着问题规模增大时的求解方法
找到求解的递归函数后，设计递归程序
动态规划
每次决策依赖于当前状态，又随机引起状态的转移。一个决策序列就是在变化的状态中产生出来的。所以，多个阶段最优化决策解决问题的过程就成为动态规划。
条件:
最优化原理
无后效性: 即某阶段状态一旦决定，就不受以后决策的影响，只与当前状态有关。
有重叠子问题: 即子问题之间不相互独立。
步骤:
划分阶段
确定状态和状态变量
确定决策并找出状态转移过程
寻找边界条件
通用模型
必须借助变量保存每个子问题的结果
设置数组边界值
找出状态转移方程，即每个状态根上一个状态的关系
应用场景
斐波那契数列
跳台阶，填充长方体问题
背包
解题思维
不管子问题是否用到，只要计算，就讲结果存储。
分析子问题是，从当前问题的状态有几种考虑，来推断与上一个状态转移的过程，从而找到转移过程
找边界条件
贪心算法
对问题求解时，总是做出在当前看来最好的选择。
贪心算法的解不代表整体最优解。
条件
最优子问题
无后效性
步骤
建立数学模型来描述问题
分解问题
子问题求解，得到子问题最优解
合并子问题题的最优解
应用场景
背包，一定容量的背包装入最大价值物品
回溯算法
类似枚举的搜索过程，主要是在搜索过程中寻找问题的解，当发现不满足求解条件时，就回溯返回，尝试别的路径。有通用解题方法的美称。
步骤
针对问题，确定解空间( 首先明确定义问题的解空间，问题的解空间至少包含问题的一个(最优)解)
确定结点的扩展搜索规则
以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索
通用模型
int a[n]，i
i = 1
while (i>0(有路可走) and (未达到目标)) {
if (i>n) {
搜索到一个解，输出
} else {
while (a[i]) {
a[i]下一个可能得值
}
if (a[i]在搜索空间内) {
标识占用的资源
i++
} else {
清理所占的状态空间
i–
}
}
}
递归
利用递归中的变量保存状态，自动恢复状态
应用场景
八皇后
分支限界
类似回溯，也是一种在问题的解空间树T上搜索问题的解法，但与回溯的求解目标不同。回溯求解目标是找出T中满足约束条件的所有解，而分支限界的求解目标是找出满足约束条件的一个解(某种意义是最优解)
采用搜索策略是广度优先。
