DFS+DP解情境模擬題: 走出邊界的方法數 Out of Boundary Paths_Leetcode #576

Héctor J. Rivas on Unsplash

題目敘述

題目會給定一個指定高度和寬的方格版，還有一顆小球的起始位置，和最大移動步數。

小球每一步可以選擇向上、下、左、右移動一格，請問小球能走到方格版界外的路徑方法數總共有幾種?

方法數可能很大，題目要求，最後回傳答案時，先對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:

[1] Out of Boundary Paths_ Python by DFS + N4 with DP