深度剖析记忆化搜索（非dp）_洛谷p1020 记忆化搜索

      序言： 

        相信许多人面对记忆化搜索(Memory search,以下简称MS)会望而却步。因为原本爆搜中的状态就具有隐蔽性，难以调试。而MS中往往存在着更多的递归回溯让人难以理解。本篇内容意在用代码层面深入递归讲解各自的调用和返回问题。

        记忆化搜索的概念许多人都已清楚，但它难就难在对"递归"，"回溯"，“记忆"，“返回”这四大关键转化为代码的理解。但这些问题仅仅是了解思想是完全不够的，学习MS一定要落实在代码上，网上有许多MS的题解，但都很少去解释为什么要这么递归和回溯，本篇将用尽可能详细的解释去落实到每一句核心语句上。

第一题：记忆化的典型应用

        开始这里就不用传统的斐波那契数列来距离了。而是用洛谷例题:P1028 [NOIP2001 普及组] 数的计算

来讲解。此题递归状态清晰易于分析，易于初学者学习。

题目大意:假设一种合法数列x1,x2,x3...n，其中x1>=x2/2, x2>=x3/2 ... (n-1)>=n/2。问给定n中合法数列有多少个。

 

 看到这题必然会想到用爆搜去做即代码如下：

#include<iostream>
using namespace std;
int res,n;
void dfs(int x)
{
	if(x==1)//当x等于一时递归结束，开始回溯
	{
		return;
	}
	for(int i=x/2;i>=1;i--)//将i初始化为x的一半来枚举，符合题意
	{
		res++;
		dfs(i);
	}
}
int main()
{
	scanf("%d",&n);
	dfs(n);
	printf("%d",res+1);//由于上述递归没有算到本身如例题中所示，此递归并没有将初始值6算入答案，因此答案需要+1。
	return 0;
}

结果:必然TLE。因为n范围1-1000，而爆搜通常是n^n，n!等时间复杂度，因此必然会爆。所以开始思考用记忆化搜索，先上代码：

#include<iostream>
using namespace std;
int book[2000];
int dfs(int x)
{
	int res=0;//疑问1:为什么变量初始化为0
	if(x==1)
	return 1;//疑问2：为什么当递归结束时返回1而不是其他值
	if(book[x]) return book[x];
	for(int i=1;i<=x/2;i++)
	{
		res+=dfs(i);//疑问3：为什么是res+=dfs(i)而不是res=dfs(i)
	}
	return book[x]=res+1;//疑问4：前面已经有了那么多return，此处return有何用，并且为什么是book[x]=res+1
}
int main()
{
	int n;
	scanf("%d",&n);
	printf("%d",dfs(n));
	return 0;
}

 首先讲一下记忆化搜索中的一些概念，函数通常以整数型进行返回，变量相较于普通暴力搜索，其变量大多为局部变量（这一点对理解后面递归和返回值十分重要）。

注意：！！！返回(return)和递归(调用自身)时会直接暂时截断掉此语句后面的语句。直到触发递归结束条件时(即准备回溯时)才继续执行此语句后面的语句！！！//注意这句话对理解多层递归(例如递归函数中多语句调用自身和多语句返回中）有极大作用。

疑问1：初始化0不会导致后面返回res都是0吗？答：不会，这里不能将其理解为main函数中循环的变量，递归时并不会因其初始化语句的存在而重置res为0。你可能还会想res直接放在全局变量不行吗，答：不行。因为res会随着递归状态的不同而改变。

疑问2：你需要先明白，当x==1时并非整个递归结束，而是函数找到了其中一个答案，因此开始回溯,以方便后面再次递归寻找第2,3,4...个答案。由于此题中当x==1时合法，因此算作答案的其一，return 1，以供后续res的完整性。

疑问3：为什么不是res=dfs(i)？首先要明白此递归函数dfs(int x)返回的是部分答案，而并非像线性运算般直接算出答案。因此要将dfs的答案累加在res中。

疑问4：此语句为什么是return book[x]=res+1 你可能会有疑问，这句到底是用来1:存储数组(记忆)还是2:返回res+1？其实这句只是合二为一的语法运用罢了，放在此处意味先执行1在执行2。那么为什么返回值是res+1。我们先来看疑问2。当x==1时找到了一种答案，因此res+1。然后开始回溯，回溯时所经过的路径仍然合法，因此我们需要在此返回res+1。然而你可能会想，上面那么多return不会影响最后那句返回值吗，答：不会，因为此时处在回溯阶段，上面的return已经暂时结束。

什么？上面讲了那么多还不明白，那直接显示返回最后一句时的状态再结合上述理解一

 当n=10时：

         可见使用记忆化搜索在此题无需进入第二层，因为在本题中第2层即可记忆所有需要的数，如第三层的:两个2和第四层的两个1都已提前在第二层中记录，因此需要用到他们时无需递归，直接返回数组中记录的答案即可。状态显示代码如下：

#include <iostream>
using namespace std;
int book[1005];
int Yes=1;
int print(int n,int step)
{
	cout<<"第"<<Yes++<<"次调用"<<"此时n为:"<<n<<"此时在第"<<step<<"层"<<endl;
	return 0;
}
int f(int n,int step){
    if(n == 1) return 1;
	if(book[n]) return book[n];
	int result = 0;
    for(int i = 1; i <= n/2; ++i)
    {
    	result += f(i,step+1);
	}
    book[n] = result + 1;//两句拆为一句也可以这样写 
    return book[n]+print(n,step);  //两句拆为一句也可以这样写，此处print函数只是为了显示状态，并不影响结果 
}
int main(){
    int n; cin>>n;
    cout<<f(n,1);
}

---

第二题：[SHOI2002] 滑雪

这是道非常经典的二维MS(记忆化搜索)题，非常适合拿来练手，但是我看网上的大多题解总是一直在解释MS的原理而抛开其代码语句的实现，因此我会在下面尽可能详细介绍每一句代码的含义。

题意：给你一个R行C列的整数型经典二维矩阵，其矩阵是一个有着许多不同高低地势的雪山，每个坐标都有相应的值，其值分别代表每个坐标的高度。现在你想仅靠重力滑雪，因此只能滑向附近上下左右四个方向，当且仅当将要滑的坐标高度低于当前坐标高度时才能滑行(即一个递减高度序列算为一个滑坡，可以进行滑行)。例如下图：

 暴力思考：找到一个最长的下降序列即可，因此直接二维暴力每个坐标为起点所在的最长下降序列即可，本题不用开bool数组记录走过的路。

#include<iostream>
using namespace std;
int n,m,ans=-1;
int ma[200][200],flag[200][200];//flag数组不需要
int tx[]={-1,1,0,0};
int ty[]={0,0,-1,1};
void dfs(int x,int y,int step)
{
	ans=max(step,ans);
	//flag[x][y]=1;
	for(int i=0;i<4;i++)
	{
		int ttx=x+tx[i],tty=y+ty[i];
		if(/*!flag[ttx][tty]&&*/ma[ttx][tty]<ma[x][y]&&ttx>=1&&ttx<=n&&tty>=1&&tty<=m)
		{
			dfs(ttx,tty,step+1);
			//flag[ttx][tty]=0;
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	scanf("%d",&ma[i][j]);
	
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	{
		dfs(i,j,1);
		//flag[i][j]=0;
	}
	printf("%d",ans);
	return 0;
}

结果90分TLE。

记忆化思考一：本题由于dfs中的两个坐标变量重要不能舍去，因此考虑是用一个二维数组book[x][y]来存储每次搜索时经过此处坐标时的最长序列。所以可以想到这样一个框架：

int dfs(int x,int y)
{
	if(book[x][y]) return book[x][y];//如果将要搜寻的坐标在之前已经搜索,也就是非0直接返回其值即可
	for(int i=0;i<4;i++)
	{
		int ttx=x+tx[i],tty=y+ty[i];
		if(ma[ttx][tty]<ma[x][y]&&ttx>=1&&ttx<=n&&tty>=1&&tty<=m)
		{
			//大脑宕机处1
		}
	}
	//大脑宕机处2
}

只要想想就知道1处一定是递归的关键代码，2处是返回值时（即回溯时）的关键代码。此处将1和2结合起来思考。我们MS是为了将返回值存入book[x][y]中，因此在1中考虑直接使book[x][y]=某个递归语句。那就简单了，直接使book[x][y]=dfs(ttx,tty)不就行了？不行！因为每次搜索会从4个方向进行搜索，而我们要求的是这四个方向的最大值。因此应使book[x][y]=max(book[x][y],dfs(ttx,tty))才对。我们现在有了递归，但是需要返回什么呢。不要设立一个递归终止条件吗？并不需要。因为我们的循环保证每一步都一定是在往下寻找。当此坐标的所有下降序列都找完时会自动结束递归并开始回溯。因此我们直接利用2处的回溯作为回溯值返回即可。防止绕进去先上代码：

int dfs(int x,int y)
{
	if(book[x][y]) return book[x][y];
	for(int i=0;i<4;i++)
	{
		int ttx=x+tx[i],tty=y+ty[i];
		if(ma[ttx][tty]<ma[x][y]&&ttx>=1&&ttx<=n&&tty>=1&&tty<=m)
		{
			book[x][y]=max(book[x][y],dfs(ttx,tty));
		}
	}
	return book[x][y]+=1;//疑问1
}

疑问1：在回溯时也就是从所探索的路径高度最低的坐标到起始坐标的过程。因为我们知道递归时所走的每一步都是有效路径，因此回溯时把当前book[x][y]的值自加1并返回即可。注意回溯时的x,y只有当最后一刻才是真正的起始x,y。也就是说在回溯时自动就记录了所经过路径的目标最长序列的最长长度。

记忆化思考二：上边的MS法一是依靠在回溯时进行记录，那么我们可以在递归时就进行记录吗？答案是可以：为节省篇幅直接上全代码讲解：

#include<iostream>
using namespace std;
int n,m;
int ma[200][200];
int book[200][200];
int tx[]={-1,1,0,0};
int ty[]={0,0,-1,1};
int dfs(int x,int y)
{//以下注释处是法一的语句
	if(book[x][y]) return book[x][y];
	book[x][y]=1;//疑问1
	for(int i=0;i<4;i++)
	{
		int ttx=x+tx[i],tty=y+ty[i];
		if(ma[ttx][tty]<ma[x][y]&&ttx>=1&&ttx<=n&&tty>=1&&tty<=m)
		{
			//book[x][y]=max(book[x][y],dfs(ttx,tty));
			book[x][y]=max(book[x][y],dfs(ttx,tty)+1);//疑问2
		}
	}
	//return book[x][y]+=1;
	return book[x][y];//疑问3
}
int main()
{
	int res=-1;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	scanf("%d",&ma[i][j]);
	
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	{
		res=max(dfs(i,j),res);
	}
	
	printf("%d",res);
	return 0;
}

疑问1,3：是不是这里似曾相识，类似第一题的初始化。但是这里的初始化对应着回溯时的语句，可以发现回溯时直接返回book[x][y]。因此我们在一开始就初始化，也就等同于方法一在返回时的自加1了。（另外思考！我们在递归时并不会改变book[x][y]的值，而是在回溯中进行改变）

疑问2：如果此处直接写成book[x][y]=max(book[x][y],dfs(ttx,tty));则会导致即使搜索并回溯完，所有book[x][y]记录的值也只是初始化时所保存的1。法一中我们解释过每一步都是有效步数，因此我们在递归时直接将返回的答案进行+1即可。

思考：仔细观察可以发现，其实法尔也是在其进行回溯时进行了+1。因为book[x][y]吸收的是dfs后的值再+1。只不过认为看起来像是递归时+1罢了。此处也对应了上面括号里的思考解答。

持续更新中......