记忆化搜索

对于一些问题而言，搜索低效的原因是没有处理好重叠子问题，但是动态规划却可以很好的处理重叠子问题。但是在一些递推关系复杂，不能很好的用 循环的实现的时候，就可以用记忆化搜索。
简单来说：

记忆化搜索 = dfs + 动态规划

一般来所，动态规划需要去遍历所有的状态，而使用记忆化搜索，就可以在搜索的过程中进行剪枝，从而避免的遍历一些无效的状态.

而对于记忆化搜索的递推函数的实现，大致有4个步骤

• 递推函数结束的边界，以及边界条件下的处理
  例如 结束递推，将我们需要的结果存储起来

• 对当前状态的检查，如果状态已经被记录，就直接返回

• 从当前状态到下一个状态的转移，记录当前状态的最优解

• 返回结果

下面的伪代码

type dfs(state，状态){
    if（边界条件）{
        dosome
        .....
        return type;
    }
    if(状态是否被记录){
        return record[state];
    }
    for(遍历接下来的状态){
        if（这个状态时合法的）{
            状态转移方程
            .....
        }
    }
    reuturn  record[state];
}