记忆化搜索

基本思想

记忆化搜索是深度优先搜索（DFS）中的一种剪枝方法，那什么是记忆化搜索呢？顾名思义，记忆化搜索就是让程序记住一些东西，然后可以在需要用的时候可以瞬间调用，不需要再进行一次复杂的计算！

怎么记？
 首先，记忆需要大脑来存储数据，什么来模拟大脑？ 数组
 其次，记忆需要现有的知识用来记住，知识从哪里来？ 以前求出的数据。
这样，我们如果要用到以前求过的数据，就可以从数组中调用，可以大大提高我们程序的运行速度

样例

斐波那契数列计算：斐波那契数列是这样的：1、1、2、3、5、8、13、21、34…… 发现规律了吗？ 第一项和第二项是1，除了前面两个数外，每一个数都是前面两个数的和。 这样的题大家应该都做过，现在我们规定一下输入输出格式。

输入格式：

一个正整数N（1≤N≤90）表示输出斐波那契数列的前N项。

输出格式：

共 N 行，每行两个正整数 i、t，表示斐波那契数列第 i 项是 t。

普通的深度优先搜索(递归求解)

#include <bits/stdc++.h> 
using namespace std;
int n; 
long long fbnq(int n)
{
	if (n==1 || n==2)
		return 1;
	return fbnq(n-1)+fbnq(n-2);
}
int main()
{
	cin >>n;
	for (int i=1;i<=n;i++)
		cout <<i <<" " <<fbnq(i) <<endl;
	return 0;
}

运行一下，发现前面 40 项还好，到了后面，速度就突然下降，90项的话大概要2000000年！ 那么，我们该怎么办？ 我们可以对这个程序计算过的数进行观察（假设当前要计算的是 fbnq(7) ）： 我们发现，这幅图中：

    7 被算了 1 次；

    6 被算了 1 次；

    5 被算了 2 次；

    4 被算了 3 次；

    3 被算了 5 次；

    2 被算了 8 次；

    1 被算了 5 次；

    这个增长率是非常可观的，除了最后一项，其他的数据正好是 斐波那契数列。

    我们知道 斐波那契数列 到达第47项，就可以超过 int 范围！ 第93项就可以超过 long long 范围！

    这么大的数，怎么可能不超时？

    再想一想，同样的东西算了很多遍，为什么不用 “大脑” 将它们 记下来呢？ 这样就不用重复计算，只需要直接调用就可以了！！！

    OK呀！

记忆化搜索 程序

#include <bits/stdc++.h> 
using namespace std;
long long n,a[100];    //数组a 为大脑，这里一点要用 long long，原因自己想
long long fbnq(int n)
{
	if (n==1 || n==2)        //前两项都是 1
		return 1;
	if (!a[n])              //如果记忆为空
		a[n]=fbnq(n-1)+fbnq(n-2);        //记住这个值
	return a[n];        //返回记忆中的值
}
int main()
{
	cin >>n;
	for (int i=1;i<=n;i++)
		cout <<i <<" " <<fbnq(i) <<endl;        //输出
	return 0;
}

这可能有人要问：为什么不直接用循环搞定呢，又方便又快捷？？ 是的，一个循环确实方便许多，但这里主要讲的是方法，这个方法在面对 用深度优先搜索 解决 但是会超时 的题目时，可能用得上。