记忆化搜索：

不论是前缀和还是dpdp，还是……

大部分算法都要有动态转移方程。

但是动态转移方程有个缺陷：

有很多动态方程会重复计算好几遍，这会使复杂度大大增加。

但用什么方法来解决此问题呢？

有些人想到了：用一个数组储存函数值。

这就是记忆化搜索。

该算法使用范围：当一个题目根据具体判断可能会出现重复的答案时候，或是不加以优化的暴力搜索会超时的时候，就可以考虑使用记忆化搜索。

e.g.斐波那契数列。

未经过优化的代码：

1
2
3
4
5
int f(int n)
{
	if(n==1||n==2) return 1;
	else f(n-1)+f(n-2);
}
费时大，许多被重复计算,要算12次。

优化代码：

1
2
3
4
5
6
7
8
9
10
long long a[10001];
int f(int n)
{
	if(n==1||n==2) return 1;
	if(a[n]==0)
	{
		return a[n]=f(n-1)+f(n-2);
	}
	else return a[n];
}

用一个数组储存f(n)f(n)的值，遇到则输出，不然赋值，只需5次，复杂度O(n)O(n)。

可以看出用了记忆化搜索，TLE少份愁！

P1464 Function\texttt{P1464 Function}

P1352 没有上司的舞会\texttt{P1352 没有上司的舞会}

U121357 找回病人\texttt{U121357 找回病人}