Leetcode Problem 2328. Number of Increasing Paths in a Grid

2328. Number of Increasing Paths in a Grid

Leetcode Solutions

DFS with Memoization

  1. Initialize a 2D array dp with the same dimensions as grid and fill it with -1 to represent unvisited cells.
  2. Define a recursive function dfs(i, j) that computes the number of increasing paths ending at grid[i][j].
    • If dp[i][j] is not -1, return dp[i][j] as the result is already computed.
    • Otherwise, set dp[i][j] to 1 (the cell itself is a path).
    • For each of the four directions (up, down, left, right), if the neighbor cell is valid and has a smaller value, increment dp[i][j] by the result of dfs on the neighbor cell.
    • Return dp[i][j].
  3. Iterate over every cell in grid and call dfs(i, j) for each cell.
  4. Sum up all values in dp to get the total number of strictly increasing paths.
  5. Return the sum modulo 10^9 + 7.
UML Thumbnail

Sorting + Dynamic Programming (DP)

Ask Question

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

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...