记忆化搜索，顾名思义吗，搜索一次记忆一次，功能
题目描述
楼梯有 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不能再分了。
我们很容易写下下面的函数：
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;
}