记忆化搜索专题

记忆化搜索专题训练

0.前言

有些时候朴素深搜会出现超时情况，所以诞生出一种记忆化搜索的dfs，其实它也是dfs，只不过在dfs的过程中，添加了赋值的过程，这个赋值的过程就叫做记忆。这里面会根据一些题目来讲解记忆化搜索。

1.样例分析

1.1 题目 络谷 P1434滑雪

1.2分析

• 找出每个坐标点 (x,y) 的最大滑雪距离，并为其赋值，若下次还搜到了这个点，这直接返回这个值，而不用再次搜索。

1.3代码

#include<iostream>

using namespace std;
const int maxN = 105;
int n,m;//行列 
int arr[maxN][maxN];//初始的二维序列
int dis[maxN][maxN];// dis[i][j]表示(i,j)能够滑行的最远距离

int getMax(int a,int b,int c,int d){//从4个整数中取最大值
	return max((max(a,b)),max(c,d) );
}

//计算（x,y）能够滑行的最远距离sum
//prior表示上一个数是多少 
int dfs(int x,int y,int prior){
	//1.如果越界 或者 高度达不到要求
	if(x<0 || x>=n || y<0 || y>=m || prior <= arr[x][y] ){
		return 0;
	}
	
	if(dis[x][y] != 0){//2.如果已经计算过，就不用再计算了，直接返回即可
		return dis[x][y]; 
	}
	
	prior = arr[x][y];	
	dis[x][y] =getMax(//3.返回四个中的最大值，并赋值给dis[x][y]
					dfs(x-1,y,prior),
					dfs(x,y+1,prior),
					dfs(x+1,y,prior),
					dfs(x,y-1,prior) )+1;
	
	//4.返回最后的计算结果（为main函数中的tempDis服务）
	return dis[x][y];
} 
 
int main(){
	cin >> n>> m;
	fill(dis[0],dis[0]+maxN*maxN,0);//初始化为0 
	int maxDis = 0;
	for(int i = 0;i<n;i++){
		for(int j = 0;j<m;j++){
			cin >> arr[i][j];			
		}
	}
			
	for(int i = 0;i<n;i++){
		for(int j = 0;j<m;j++){
			//(i,j) 
			int tempDis = dfs(i,j,9999);//深搜 
			if(maxDis < tempDis ){
				maxDis = tempDis;//深搜 
			}
		}
	}
	
	cout << maxDis<<"\n";
} 

1.4 测试用例：

3 3 
1 1 3
2 3 4
1 1 1
4

2.反例分析

是不是什么情况都适合使用记忆化搜索呢？肯定不是！
今天在写到络谷的一道题【
[USACO08JAN]牛大赛Cow Contest 】时，想着是不是可以使用记忆化搜索。举例如下。
输入样例：奶牛4打败了2，2又打败了1，5打败了2 。
这样我们就可以记录win[1]=0，win[2]=1，win[4]=2。等第搜索5时，发现2已经搜索过了，直接返回 win[2]+1 = 2 ，这样就算出来了win[5]=2。但是这样真的合适吗？就拿题中给出的测试用例：

5 5
4 3
4 2
3 2
1 2
2 5

这时记忆化搜索就行不通了，原因是会 出现重复计算。
假设先计算奶牛2，发现奶牛2胜过的牛有1头（即win[2]=1)。
计算3时，2已经计算过了，直接返回win[2]+1 = 2；计算4时，因为4即可到2，又可到3，且他们都已经访问过了，所以有win[4] += (win[2]+1) = 3;，win[4] += (win[3]+1) =5;就产生了重复计算的问题。