我们发现假如有时候使用递归或者深搜的时候数据量比较大的时候计算速度非常缓慢，而且可以发现最重要的是递归的时候存在重复子问题的重复求解了，比如像斐波拉契数列的求解f(n) = f(n - 1) + f(n - 2)就存在着重复子问题的重复求解f(n - 1)继续递归下去的时候那么又会重复计算f(n - 2)，这样假如数据量大的话耗时非常大，而且我们可以发现存在着像斐波拉契这样一类具有这样通项公式的递归形式问题的求解往往存在着很多重复子问题的重复求解，假如能够把计算过的子问题的值保存起来那么计算之前查询一下如果发现计算过那么直接返回了，不用搜索下去了
这样便会大大降低时间的复杂度，这个有点类似了深度优先搜索的剪枝，但是又有点同，dfs通常使用if条件来进行提前的剪枝，不满足条件的搜索那么接下来的支路都会剪断，而这里是递归之前进行查询，递归之后进行保存那么就可以达到解决我们重复子问题重复求解的问题了
像斐波拉契数列求解的过程： 最后的f(2)递归调用f(1)和f(0)那么当递归调用退回来之后记录的是便是f(2)的值，再退回来记录的是f(3)的值，f(2)的值，f(4)的值…
记忆型的递归特别是针对重复子问题的重复求解的问题，当我们发现问题可以使用递归来求解，而且存在重复的子问题那么可以使用记忆型的递归来解决，这样便可以大大减少搜索的时间，像上面的f(5)的求解左边的递归完成之后都不需要进行右边的递归直接返回就可以了
斐波拉契数列记忆型的求解代码如下：
// 递归求斐波那契数列 public class Solution1 { private int num = 0; public int fib( int n ){ num ++; if( n == 0 ) return 0; if( n == 1 ) return 1; return fib(n-1) + fib(n-2); } public int getNum(){ return num; } }记忆化搜索版本
import java.util.Arrays; // 记忆化搜索 public class Solution2 { private int num = 0; public int fib(int n){ int[] memo = new int[n + 1]; Arrays.fill(memo, -1); return fib(n, memo); } private int fib(int n, int[] memo){ num ++; if(n == 0) return 0; if(n == 1) return 1; if(memo[n] == -1) memo[n] = fib(n - 1, memo) + fib(n - 2, memo); return memo[n]; } } import java.util.Arrays; // 动态规划 public class Solution3 { public int fib(int n){ int[] memo = new int[n + 1]; Arrays.fill(memo, -1); memo[0] = 0; memo[1] = 1; for(int i = 2 ; i <= n ; i ++) memo[i] = memo[i - 1] + memo[i - 2]; return memo[n]; } }