Leetcode Problem 576. Out of Boundary Paths

576. Out of Boundary Paths

Leetcode Solutions

Dynamic Programming Approach

  1. Initialize a 2D array dp with dimensions m x n and set all values to 0.
  2. Set dp[startRow][startColumn] to 1, as there is one way to be at the starting position with 0 moves.
  3. Iterate from 1 to maxMove, updating the dp array for each number of moves: a. Create a temporary 2D array temp with dimensions m x n and set all values to 0. b. Iterate over each cell (i, j) in the dp array: i. For each of the four directions (up, down, left, right), check if moving in that direction would go out of bounds. ii. If it goes out of bounds, increment the count of paths leading out. iii. If it doesn't go out of bounds, update temp[i][j] by adding the number of ways to reach the adjacent cell from the previous move. c. After updating all cells, copy temp to dp for the next iteration.
  4. Return the total count of paths leading out of the grid, modulo 10^9 + 7.
UML Thumbnail

Recursion with Memoization Approach

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...