在洛谷 “滑雪” P1434题解——DP中介绍了这道题的动态规划解法，下面介绍的则是记忆化搜索。事实上我也是dp的初学者，我决定用这道经典的题目来体会dp和记忆化的正真思路。未来会对dp以及记忆化搜索进行总结。

首先先亮出喜闻乐见的大爆搜。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;
int n,m;
int i,j;
int d[105][105],a[105][105];
int maxn;
void dfs(int dep,int x,int y)
{
maxn=max(dep,maxn);//取最大深度
        //四个方向进行遍历
if (a[x+1][y]<a[x][y]) dfs(dep+1,x+1,y);
if (a[x-1][y]<a[x][y]) dfs(dep+1,x-1,y);
if (a[x][y+1]<a[x][y]) dfs(dep+1,x,y+1);
if (a[x][y-1]<a[x][y]) dfs(dep+1,x,y-1);
}
int main()
{
    scanf("%d %d",&n,&m);
    int k=0,t;
    for (i=1;i<=n;i++)
      for (j=1;j<=m;j++)
        cin>>a[i][j];
    for (i=1;i<=n;i++)
      for (j=1;j<=m;j++)
        dfs(0,i,j);
    cout<<maxn<<endl;
    return 0;
}

这个普通的深度优先搜索会在同一个点反复求其的最大值，浪费了许多时间，因此我们使用记忆化搜索对已经遍历过的点进行记录，如果发现已经遍历过了，那么就无需再次搜索，这将大大降低时间复杂度。

PS：这里要吐槽Luogu的评测系统真垃圾

一个大爆搜居然能拿到90分？？？究竟是道德的沦丧还是人性的扭曲

记忆化搜索实际上是递归来实现的，但是递归的过程中有许多的结果是被反复计算的，这样会大大降低算法的执行效率。

而记忆化搜索是在递归的过程中，将已经计算出来的结果保存起来，当之后的计算用到的时候直接取出结果，避免重复运算，因此极大的提高了算法的效率。

在这道题目中我们需要保存的结果很显然就是每个点所能遍历到的最大深度。

代码如下，请看注释:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
int n,m;
int i,j;
int d[105][105],a[105][105];
int maxn;
int dfs(int dep,int x,int y)
{
if (d[x][y]!=1)
return d[x][y];//如果这个点已经搜索过了，那么直接返回
int ans=0;//ans初始化一定要是0
if (a[x+1][y]<a[x][y]) ans=max(ans,dfs(dep+1,x+1,y)+1);
if (a[x-1][y]<a[x][y]) ans=max(ans,dfs(dep+1,x-1,y)+1);
if (a[x][y+1]<a[x][y]) ans=max(ans,dfs(dep+1,x,y+1)+1);
if (a[x][y-1]<a[x][y]) ans=max(ans,dfs(dep+1,x,y-1)+1);
d[x][y]=max(d[x][y],ans);
return d[x][y];
}
int main()
{
    scanf("%d %d",&n,&m);
    int k=0,t;
    for (i=0;i<=n+2;i++)
      for (j=0;j<=m+2;j++)
      {
        a[i][j]=INT_MAX;
        d[i][j]=1;
      }
    for (i=1;i<=n;i++)
      for (j=1;j<=m;j++)
        cin>>a[i][j];
    maxn=0;
    for (i=1;i<=n;i++)
      for (j=1;j<=m;j++)
        maxn=max(dfs(1,i,j),maxn);
    cout<<maxn<<endl;
    return 0;
}