NeetCode #736LC-576Medium2-D Dynamic Programming
← Back to All Problems#736 · #576 · Out of Boundary Paths(出界的路径数)
📌 Problem Statement & Constraints
A ball sits at
(startRow, startColumn) of an m x n grid. In one move it moves to one of the four adjacent cells. Return the number of distinct move sequences that take the ball out of the grid in at most maxMove moves, modulo 1e9+7. Constraints: 1 <= m, n <= 50, 0 <= maxMove <= 50, and the start cell is inside the grid.💡 Core Algorithmic Approaches
- Define
dp[k][i][j]= the number of paths that leave the grid starting from(i, j)withkmoves remaining. The base isdp[0][i][j] = 0. - For each of the four directions, if the neighbour is outside the grid the move exits immediately and contributes 1; otherwise it contributes
dp[k-1][neighbour]. - The recurrence is
dp[k][i][j] = sum over 4 neighbours (1 if outside else dp[k-1][n_i][n_j]). - The answer is
dp[maxMove][startRow][startColumn]; iteratingkfrom 1 upward fills the table inmaxMovelayers.
💻 Benchmark Python3 Implementation
class Solution:
def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
MOD = 10**9 + 7
dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
dp = [[0] * n for _ in range(m)]
for _ in range(maxMove):
nxt = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
total = 0
for di, dj in dirs:
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n:
total += dp[ni][nj]
else:
total += 1 # this single move already exits
nxt[i][j] = total % MOD
dp = nxt
return dp[startRow][startColumn] % MOD⚡ Complexity Deep Dive
⏱️ Time Complexity
O(maxMove * m * n): each layer visits every cell with four constant-time transitions.
💾 Space Complexity
O(m * n): two grid layers.
⚠️ Interview Pitfalls & Follow-ups
- Counting only paths of exactly
maxMovesteps: the ball may exit earlier, so exits are counted at every step via the+1for out-of-grid neighbours. - Recursing without memoisation: the number of paths grows exponentially, so a plain DFS times out.
- Forgetting the modulo on each addition: counts blow up far beyond 64 bits.
- Reversing the DP direction:
dp[k][i][j]counts paths from(i, j), which makes the base case zero and the answer a single cell lookup.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.