問題描述
小袁非常喜歡滑雪， 因為滑雪很刺激。為了獲得速度，滑的區域必須向下傾斜，而且當你滑到坡底，你不得不再次走上坡或者等待升降機來載你。 小袁想知道在某個區域中最長的一個滑坡。區域由一個二維數組給出。數組的每個數字代表點的高度。如下： 
一個人可以從某個點滑向上下左右相鄰四個點之一，當且僅當高度減小。在上面的例子中，一條可滑行的滑坡為24-17-16-1。當然25-24-23-...-3-2-1更長。事實上，這是最長的一條。
你的任務就是找到最長的一條滑坡，並且將滑坡的長度輸出。 滑坡的長度定義為經過點的個數，例如滑坡24-17-16-1的長度是4。
輸入格式
輸入的第一行表示區域的行數R和列數C(1<=R, C<=10)。下面是R行，每行有C個整數，依次是每個點的高度h（0<= h <=10000）。
輸出格式
只有一行，為一個整數，即最長區域的長度。
樣例輸入
5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
樣例輸出
25
解決一道題前 首先考慮用什麼算法
對於這道題而言 最直接樸素的想法應該是對於每個點進行深搜或者廣搜 最後枚舉一遍答案
但是注意 對於每個點而言 只要周圍的點比他小 都可以被走到 因此這樣做的話時間復雜度是指數級別的 AC不掉
那麼我們考慮優化
首先 搜索的思路是沒有錯的 那麼怎樣優化它呢
我們觀察到一個條件 那就是 某個點只能從數值更大的點轉移過來 也就是說 整個答案序列應該是遞減的 => 搜索時不可能出現循環 => 搜索順序是具有拓撲結構的 即 在一個固定答案序列中 數值較小的點一定是在數值較大的點後被搜索到 那麼我們就可以使用記憶化搜索了（注意上述所說：具有拓撲序是使用記憶化搜索的必備條件）
我們用一個數組儲存從每個點出發可以達到的最大長度，之後，若是從其他數值較大的點轉移到這個點時，不必再往後搜索了，因為結果已經記錄在數組中了，直接返回就好
注：記憶化搜索可以看作 普通搜索+大剪枝
上代碼～～
n,m = map(int,input().split())
Map = []
ans = 0
for i in range(n) : Map.append(list(map(int,input().split())))
dp = [[-1 for i in range(m)]for j in range(n)]
def dfs(x,y) :
global dp
if dp[x][y] != -1 : return dp[x][y] # 搜索過了直接返回
t = 1 # 最小就是1 即為本身
for i,j in [(1,0),(0,1),(-1,0),(0,-1)] :
px = x + i ; py = y + j
if 0 <= px < n and 0 <= py < m and Map[px][py] < Map[x][y] :
t = max(dfs(px,py)+1,t) # 更新當前點能到的最遠距離
dp[x][y] = t
return t
for i in range(n) :
for j in range(m) :
dfs(i,j)
for i in range(n) :
for j in range(m) :
ans = max(ans,dp[i][j])
print(ans)看到這裡 是不是對記憶化搜索有了深一步了解呢
再做一道拓展題鞏固一下吧！
題目鏈接：691. 立方體IV - AcWing題庫
分析過程完全相同 只不過轉移條件發生了小小的變化 下一個點必須比上一個點大1
注意一下輸出格式即可
T = int(input())
def dfs(x,y) :
global dp
if dp[x][y] != -1 : return dp[x][y]
t = 1
for i,j in [(1,0),(0,1),(-1,0),(0,-1)] :
px = x + i ; py = y + j
if 0<=px<S and 0<=py<S and Map[px][py] == Map[x][y] + 1 :
t = max(t,dfs(px,py)+1)
dp[x][y] = t
return t
for _ in range(T) :
S = int(input())
Map = []
for i in range(S) : Map.append(list(map(int,input().split())))
dp = [[-1 for i in range(S)]for j in range(S)]
ans = 0 ; idx = -1
for i in range(S) :
for j in range(S) :
dfs(i,j)
for i in range(S) :
for j in range(S) :
if ans < dp[i][j] or ans == dp[i][j] and idx > Map[i][j] :
ans = dp[i][j] ; idx = Map[i][j]
txt = 'Case #{}: {} {}'
print(txt.format(_,idx,ans))
