博客

什么是记忆化搜索呢？搜索的低效在于没有能够很好地处理重叠子问题；动态规划虽然比较好地处理了重叠子问题，但是在有些拓扑关系比较复杂的题目面前，又显得无奈。记忆化搜索正是在这样的情况下产生的，它采用搜索的形式和动态规划中递推的思想将这两种方法有机地综合在一起，扬长避短，简单实用，在信息学中有着重要的作用。

记忆化搜索,我们在dfs过程中对于一已经搜索过的点，就不必再去搜索，直接返回，大大提高了搜索的效率


相比于常规的dfs算法,不用一条路搜到底，我们只需要在之前搜索过的点停止搜索即可。

python代码

我们在使用python的过程中，一定要注意对时间的把握，因为python代码慢


AC代码

global msg,f
global r,c
r,c=map(int,input().split())

xc=[0,-1,1,0]
yc=[-1,0,0,1]
def check(i,j):
    if 0<=i<r and 0<=j<c:
        return True
    return False

def dfs(x,y):
    ans=1
    for i in range(4):
        if check(x+xc[i],y+yc[i]) and msg[x+xc[i]][y+yc[i]]<msg[x][y]:
            if f[x+xc[i]][y+yc[i]]!=-1:
                ans=max(ans,f[x+xc[i]][y+yc[i]]+1)
            else:
                tmp=dfs(x+xc[i],y+yc[i])
                f[x+xc[i]][y+yc[i]]=tmp
                ans=max(ans,tmp+1)
    f[x][y]=ans
    return ans
f=[[-1 for i in range(c)] for j in range(r)]
msg=[0]*r
for i in range(r):
    msg[i]=list(map(int,input().split()))

ans=0
for i in range(r):
    for j in range(c):
        ans=max(ans,dfs(i,j))

print(ans)