原文轉載自「劉悅的技術部落格」v3u.cn/a_id_168
現在很多網際網路企業學聰明瞭，知道應聘者有目的性的刷Leetcode原題，用來應付演算法題面試，所以開始對這些題進行“魔改”，比如北京某電商平臺的這道題：
有一個正方形的島，使用二維方形矩陣表示，島上有一個醉漢，每一步可以往上下左右四個方向之一移動一格，如果超出矩陣範圍他就死了，假設每一步的方向都是隨機的(因為他是醉的)，請計算n步以後他還活著的概率。
例如：輸入矩陣大小2*2，起點(0,0)，隨機走出一步 n = 1
輸出0.5 也就是有一半的機率還活著
例如：輸入矩陣大小3*3，起點(1,1)，隨機走出一步 n = 1
輸出1 也就是百分之百還活著
複製程式碼乍一看有點懵，但是提取關鍵字：二維矩陣、上下左右四個方向、矩陣範圍、n步，有沒有感到很熟悉？刷過Leetcode的同學一定已經聯想到了Leetcode原題第576題：出界的路徑數，難度等級為中等。
給定一個 m × n 的網格和一個球。球的起始座標為(i,j)，你可以將球移到相鄰的單元格內，或者往上、下、左、右四個方向上移動使球穿過網格邊界。但是，你最多可以移動N次。找出可以將球移出邊界的路徑數量。答案可能非常大，返回 結果 mod 109+ 7 的值。
和魔改版的題聯絡起來，所謂醉漢“死了”，其實就是移出邊界，而每走一步都會有四種可能，所以所謂的“存活率”也就是當我們算出移出邊界的路徑數量之後，再除以方向的基數4，就可以算出“存活率”，相反也可以推算“死亡率”，歸根結底，魔改版題的題眼還是算出移出邊界的路徑數，並不是最後問的“存活率”問題，這題只是用了一個並不是很講究的障眼法，很有可能是該電商平臺老闆讓手下的某個研發出道演算法題招人用，而該研發已經被需求搞的暈頭轉向，無奈之下隨便從leetcode複製了一道出來，隨便改了改。
至於解法，下意識想到並且非常好理解的解法就是利用BFS(Breadth First Search 廣度優先)，因為醉漢最多隻能移動N次，我們只要bfs依次遍歷如果發現出界，就代表死亡，進行累加1，當bfs的深度大於N的時候break結束。理論上是沒有任何問題。
import collections
def how_likely_alive(m,n,N,i,j):
mod = 10**9 + 7
Q = collections.deque([(i,j,0)])
res = 0
while Q:
x,y,step = Q.popleft()
if step > N: break
if 0<=x<m and 0<=y<n:
Q.append((x+1,y,step+1))
Q.append((x-1,y,step+1))
Q.append((x,y+1,step+1))
Q.append((x,y-1,step+1))
else:
res += 1
num = res % mod
if num == 0:
return 1
else:
return num / 4
print(how_likely_alive(2,2,1,0,0))
複製程式碼一般情況下，如果該崗位的技術要求並不高，使用bfs基本就算過關了，但是如果面試官想來一次壓力面試（所謂壓力面試就是想探探你的底），看看你的極限在哪裡，就會要求你用效率更高的演算法來解題。（這裡需要簡單分辨一下壓力面試還是故意刁難，壓力面試如果不會的話，禮貌詢問就能拿到答案，而如果連面試官都不知道面試的答案，那肯定就是故意刁難了，也就沒有面下去的必要了）。
我們再回到題目中想一想，魔改版題目並沒有定義醉後隨機走的步數N的範圍，假設N的取值範圍達到了50，我們對任意一個座標點bfs有四個方向進行遍歷，同時考慮往回走的可能性，那麼複雜度達到了N的四倍，這個效率顯然不會令人滿意，所以當N相對小的情況下,比如只走1步，bfs是最優解，而範圍過大就需要考慮dp了。
dp(Dynamic Programming)演算法即是業界大名鼎鼎的動態規劃演算法了，其核心思路是把一個複雜的大問題拆成若干個子問題，通過解決子問題來逐步解決大問題，是不是和分治法有點像？關於分治演算法可以參考這篇文章：當我們談論演算法我們在談論什麼:由疫情核酸檢測想到的分治演算法(Divide-and-Conquer),但是和分治法有區別的地方是，使用動態規劃思想有個前提：當且僅當每個子問題都是離散的（即每個子問題都不依賴於其他子問題時），才能使用動態規劃。
再次回到題目，假設這個醉漢在第 N 步到達 (mi, nj) 位置有 dp[N][mi][nj] 種路徑，可以假設一下當前狀態如何從上一步移動中得來。其實就是上下左右四個方向移動過來的，而移動步數則是 N-1。
def how_likely_alive(m, n, N, i, j):
tmp=[[[0 for i in range(n)] for j in range(m)] for k in range(N+1)]
for k in range(1,N+1):
for p in range(m):
for q in range(n):
if 0==p:
up=1
else:
up=tmp[k-1][p-1][q]
if m-1==p:
down=1
else:
down=tmp[k-1][p+1][q]
if 0==q:
left=1
else:
left=tmp[k-1][p][q-1]
if n-1==q:
right=1
else:
right=tmp[k-1][p][q+1]
tmp[k][p][q]=(up+down+left+right)%1000000007
num = tmp[N][i][j]
if num == 0:
return 1
else:
return num / 4
return num
print(how_likely_alive(2,2,1,0,0))
複製程式碼結語：Leetcode演算法題浩如煙海，想要每一道題都瞭如指掌，個人感覺難度不小，但是從這道二維矩陣中的醉漢來看，企業就算想要“魔改”，也是萬變不離其宗，多多少少都有跡可循，所以我們在刷題的過程中，應該本著寧缺毋濫的原則，真實的掌握演算法核心思想，才能夠做到舉一反三、百戰不殆。
原文轉載自「劉悅的技術部落格」 v3u.cn/a_id_168