題目敘述
題目會給定一個指定高度和寬的方格版，還有一顆小球的起始位置，和最大移動步數。
小球每一步可以選擇向上、下、左、右移動一格，請問小球能走到方格版界外的路徑方法數總共有幾種?
方法數可能很大，題目要求，最後回傳答案時，先對10^9+7做除法取餘數再回傳。測試範例
Example 1:
Input: m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0
Output: 6
Example 2:
Input: m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1
Output: 12
約束條件
Constraints:
1 <= m, n <= 50
板子的高度和寬度都介於1~50之間。
0 <= maxMove <= 50
最大移動步數介於0步和50步之間。
0 <= startRow < m
小球的起始位置的y座標一定在界內。
0 <= startColumn < n
小球的起始位置的x座標一定在界內。
演算法
這題滿直覺，可以想到就用遊戲規則和DFS深度優先搜索來進行情境模擬。
從小球指定的初始位置出發，每步可以往上、下、左、右移動一格，最多可以移動maxMove步。
當小球成功移動到界外時，代表找到一條走出邊界的方法數。
動態更新過程中，把每次當下的狀態(x, y, step)和紀錄到的答案儲存在DP table，避免重複計算，進而提升程式執行效率。
程式碼
class Solution:
def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
# Generate N4 neighborhood vector: North, East, South, West
N4 = tuple( vector for vector in itertools.pairwise([0, 1, 0, -1, 0]) )
# DP table to keep path count of getting out of boundary
dp = {}
def move(x, y, step=0):
## Look-up DP table to avoid repeated computation
if (x, y, step) in dp:
return dp[x, y, step]
## Base case:
# out of boundary, we find one path
if x < 0 or x >= n or y < 0 or y >= m :
dp[x, y, step] = 1
return 1
## Base case:
# No available step anymore
if step == 0:
dp[x, y, step] = 0
return 0
## General cases
# Explore the map with N4 neighborhood vector
count = 0
for dx, dy in N4:
count += move(x+dx, y+dy, step-1) % (10**9+7)
dp[x, y, step] = count % (10**9+7)
return dp[x, y, step]
# ======================================================
# Start DFS visiting from starting point with given max steps
return move(x=startColumn,y=startRow, step=maxMove)
複雜度分析
令
h = 板子的高度
w =板子的寬度
S = 最大可移動步數
時間複雜度:
用DFS來模擬小球的移動過程，探索整張板子，並且把每個狀態(x, y, step)對應到的答案紀錄在DP table中，避免重複搜索，所需時間為O(h * w * S)
空間複雜度:
DP table 會需要儲存每一個(x, y, step)狀態所對應的答案，最大所需空間為O(h * w * S)
關鍵知識點
動態更新過程中，把每次當下的狀態(x, y, step)和紀錄到的答案儲存在DP table，避免重複計算，進而提升程式執行效率。
為什麼要這個做? 因為格子點有可能會重複拜訪，假如沒有把每個狀態的答案存起來，會有冗餘的重複計算，造成run-time time-out超過平台所設定的時間限制。
Reference:
