记忆化搜索，顾名思义吗，搜索一次记忆一次，功能

题目描述

楼梯有 NN 阶，上楼可以一步上一阶，也可以一步上二阶。

编一个程序，计算共有多少种不同的走法。

就是提高效率呗。

 很容易看出就是个递推呗，斐波那契数列。那这道题数据很大，一次一次的递推会超限

没啥好说的就是高精的斐波那契，前面也有写到。

P1002 [NOIP2002 普及组] 过河卒 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P1002

 定义一个二维数组f（i，j）表示走到（i，j）的方案数，显然f（i，j）=f（i-1，j）+f（i，j-1）。

当卒从起点开始笔直地向下或笔直地向右，无论走多远都只有一种方法，所以当k>=0,f(0,k)=f(k,0)=1;这里值得注意的是f（0，0）=1，（自己想一想为什么），不要问我，因为我也不是很清楚。。。。。这儿就是递归的初始条件。

定义二维数组搜索马周围的控制点，赋值为1.

#include<bits/stdc++.h>
using namespace std;
int d[9][2] = { -2,-1,0,0,1,2,1,-2,-1,2,-1,-2,2,1,2,-1,-2,1 };
int cc[22][22];
long long f[22][22];
int main()
{
	int x, y, n, m;
	cin >> x >> y >> n >> m;
	for (int i = 0; i < 9; i++)
	{
		int tempx = n + d[i][0], tempy = m + d[i][1];
		if (tempx >= 0 && tempx <= x && tempy >= 0 && tempy <= y)
			cc[tempx][tempy] = 1;
	}
	f[0][0] = 1 - cc[0][0];
	for(int i=0;i<=x;i++)
		for (int j = 0; j <= y; j++)
		{
			if (cc[i][j] == 1)
				continue;
			if (i)//如果不在横轴上
				f[i][j] += f[i - 1][j];
			if (j)//如果不在纵轴上
				f[i][j] += f[i][j - 1];
	}
	cout << f[x][y];
		return 0;
}

P1044 [NOIP2003 普及组] 栈 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P1044

递推思想：假设i个元素有f（i）种方法，要求n个元素的出管方式，依题意，每个元素都有可能最后一个出去，那我们假设第k个小球最后一个出去有h（k）种方法，那么比k早入管且早出去的有k-1个数，则有f（k-1）种，比k晚出管且早出去的有f（n-k）种。独立性，所以h（k）=f（k-1)*f(n-k)

 那么每个元素都有机会最后一次出管，所以f(n)=h(1)+h(2)+   +h(n-1)+h(n)=f(0)*f(n-1)+f(1)*f(n-2)+ 

    +f(n-2)*f(1)+f(0)*f(n-1).

代码实现起来就很简单了。如下。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{//i个元素有f【i】钟出管方式
	int n;
	cin >> n;
	int  f[20] = { 1,1,2 };
	
	for (int i = 3; i <= n; i++)
	{
		for (int j = 0; j < n; j++)
			f[i] += f[j] * f[i - j - 1];
	}
	cout << f[n];
	return 0;
}

                                               接下来就是递归和记忆化搜索了

题目描述

我们要求找出具有下列性质数的个数(包含输入的正整数 nn)。

先输入一个正整数 nn(n \le 1000n≤1000),然后对此正整数按照如下方法进行处理：

1. 不作任何处理；

2. 在它的左边加上一个正整数,但该正整数不能超过原数的一半；

3. 加上数后,继续按此规则进行处理,直到不能再加正整数为止。

思路很简单，把一个数一直分下去，加不加左边跟这题没关系，函数递归地结束条件为分到1不能再分了。

我们很容易写下下面的函数：

int ss(int x)
{
	int ans = 1;
	if (x==-1)
		return 1;
	for (int i = 1; i <= x / 2; i++)
		ans += ss(i);
	return ans;
}

当然并没有什么问题，但是只能通过数据小的，运行效率低会时间超限，举个例子，比如说我们递归ss（2），它可能也会被ss（8）,ss(4)调用,但是ss（2）的值是一只不变的，在这却被重复计算了很多次。既然它的值是不变的，我们算一个保存一个，下次直接调用，不用再一直递归下去了。

这就是记忆化搜索。

将数组初始化为-1，代表没被搜索保存过。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int d[1005];
int ss(int x)
{
	int ans = 1;
	if (d[x]!=-1)
		return d[x];
	for (int i = 1; i <= x / 2; i++)
	{
		ans += ss(i);
	}
	return d[x]=ans;
}
int main()
{
	int n;
	cin >> n;
	memset(d, -1, sizeof(d));
	d[1] = 1;
	int ans = ss(n);
	cout << ans;
	return 0;
}

P1928 外星密码 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P1928这题很容易想到用函数来实现递归，但是能不能实现就是另一回事了，，，，

我们直接输入一个字符串不好查找后面，那就一个一个输，又是一个小技巧。

举个例子：AC[3FUN]

首先，我们找到了被压缩的字符串：3FUN

对3FUN进行解压，得到FUNFUNFUN

再把原来的字符串AC后面添上FUNFUNFUN即可。

由于这个只有一重「压缩」，可能递归思想体现的不太明显，这里再举一个多重「压缩」的例子：

SAD[4MLE[2TLE[2RE[2WA]]]

首先找到被「压缩」的部分：

[2MLE[2TLE[2RE[2WA]]]]

（从此处开始剩下的部分就是递归的内容了，全部由程序自主实现）

对这个部分进行解压，找到被「压缩」的部分：

[2TLE[2RE[2WA]]]

再对这个部分进行解压，找到被「压缩」的部分：

[2RE[2WA]]

再对这个部分进行解压，找到被「压缩」的部分：

[2WA]

（开始一层一层跳出递归）

对这个部分进行解压并加到前一个字符串的末尾：

[2REWAWA]

再对这个部分进行解压并加到前一个字符串的末尾：

[2TLEREWAWAREWAWA]

再对这个部分进行解压并加到前一个字符串的末尾：

[2MLETLEREWAWAREWAWATLEREWAWAREWAWA]

再对这个部分进行解压并加到前一个字符串的末尾：

SADMLETLEREWAWAREWAWATLEREWAWAREWAWAMLETLEREWAWAREWAWATLEREWAWAREWAWA

至此，递归结束，「密码」破译完毕。

所以，我们只需要找到被「压缩」的子串，并把这个字符串扔给「解压缩」程序即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
string xx()
{
	string s="",x;
	char c;
	int d;
	while (cin >> c)
	{
		if (c == '[')//发现一个压缩区
		{
			cin >> d;
			x = xx();
			while (d--)
				s += x;
		}
		else if (c == ']')
			return s;
		else
			s += c;
	}
	return s;
}
int main()
{
	cout << xx();
	return 0;
}