Question

2328. Number of Increasing Paths in a Grid

中文文档

Description

You are given an m x n integer matrix grid, where you can move from a cell to any adjacent cell in all 4 directions.

Return _the number of strictly increasing paths in the grid such that you can start from any cell and end at any cell. _Since the answer may be very large, return it modulo 109 + 7.

Two paths are considered different if they do not have exactly the same sequence of visited cells.

 

Example 1:

Input: grid = [[1,1],[3,4]]
Output: 8
Explanation: The strictly increasing paths are:
- Paths with length 1: [1], [1], [3], [4].
- Paths with length 2: [1 -> 3], [1 -> 4], [3 -> 4].
- Paths with length 3: [1 -> 3 -> 4].
The total number of paths is 4 + 3 + 1 = 8.

Example 2:

Input: grid = [[1],[2]]
Output: 3
Explanation: The strictly increasing paths are:
- Paths with length 1: [1], [2].
- Paths with length 2: [1 -> 2].
The total number of paths is 2 + 1 = 3.

 

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 1000
• 1 <= m * n <= 105
• 1 <= grid[i][j] <= 105

Solutions

Solution 1: DFS + Memorization

We design a function $dfs(i, j)$, which represents the number of strictly increasing paths that can be reached from the grid graph starting at the $i$-th row and $j$-th column. Then the answer is $\sum_{i=0}^{m-1} \sum_{j=0}^{n-1} dfs(i, j)$. In the search process, we can use a two-dimensional array $f$ to record the calculated results to avoid repeated calculation.

The calculation process of the function $dfs(i, j)$ is as follows:

• If $f[i][j]$ is not $0$, it means that it has been calculated, and $f[i][j]$ is returned directly;
• Otherwise, we initialize $f[i][j] = 1$, and then enumerate the four directions of $(i, j)$. If the grid $(x, y)$ in a certain direction satisfies $0 \leq x \lt m$, $0 \leq y \lt n$, and $grid[i][j] \lt grid[x][y]$, we can start from the grid $(i, j)$ to the grid $(x, y)$, and the number on the path is strictly increasing, so $f[i][j] += dfs(x, y)$.

Finally, we return $f[i][j]$.

The answer is $\sum_{i=0}^{m-1} \sum_{j=0}^{n-1} dfs(i, j)$.

The time complexity is $O(m \times n)$, and the space complexity is $O(m \times n)$. Where $m$ and $n$ are the number of rows and columns in the grid graph, respectively.

class Solution:
  def countPaths(self, grid: List[List[int]]) -> int:
    @cache
    def dfs(i: int, j: int) -> int:
      ans = 1
      for a, b in pairwise((-1, 0, 1, 0, -1)):
        x, y = i + a, j + b
        if 0 <= x < m and 0 <= y < n and grid[i][j] < grid[x][y]:
          ans = (ans + dfs(x, y)) % mod
      return ans

    mod = 10**9 + 7
    m, n = len(grid), len(grid[0])
    return sum(dfs(i, j) for i in range(m) for j in range(n)) % mod

class Solution {
  private int[][] f;
  private int[][] grid;
  private int m;
  private int n;
  private final int mod = (int) 1e9 + 7;

  public int countPaths(int[][] grid) {
    m = grid.length;
    n = grid[0].length;
    this.grid = grid;
    f = new int[m][n];
    int ans = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        ans = (ans + dfs(i, j)) % mod;
      }
    }
    return ans;
  }

  private int dfs(int i, int j) {
    if (f[i][j] != 0) {
      return f[i][j];
    }
    int ans = 1;
    int[] dirs = {-1, 0, 1, 0, -1};
    for (int k = 0; k < 4; ++k) {
      int x = i + dirs[k], y = j + dirs[k + 1];
      if (x >= 0 && x < m && y >= 0 && y < n && grid[i][j] < grid[x][y]) {
        ans = (ans + dfs(x, y)) % mod;
      }
    }
    return f[i][j] = ans;
  }
}

class Solution {
public:
  int countPaths(vector<vector<int>>& grid) {
    const int mod = 1e9 + 7;
    int m = grid.size(), n = grid[0].size();
    int f[m][n];
    memset(f, 0, sizeof(f));
    function<int(int, int)> dfs = [&](int i, int j) -> int {
      if (f[i][j]) {
        return f[i][j];
      }
      int ans = 1;
      int dirs[5] = {-1, 0, 1, 0, -1};
      for (int k = 0; k < 4; ++k) {
        int x = i + dirs[k], y = j + dirs[k + 1];
        if (x >= 0 && x < m && y >= 0 && y < n && grid[i][j] < grid[x][y]) {
          ans = (ans + dfs(x, y)) % mod;
        }
      }
      return f[i][j] = ans;
    };
    int ans = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        ans = (ans + dfs(i, j)) % mod;
      }
    }
    return ans;
  }
};

func countPaths(grid [][]int) (ans int) {
  const mod = 1e9 + 7
  m, n := len(grid), len(grid[0])
  f := make([][]int, m)
  for i := range f {
    f[i] = make([]int, n)
  }
  var dfs func(int, int) int
  dfs = func(i, j int) int {
    if f[i][j] != 0 {
      return f[i][j]
    }
    f[i][j] = 1
    dirs := [5]int{-1, 0, 1, 0, -1}
    for k := 0; k < 4; k++ {
      x, y := i+dirs[k], j+dirs[k+1]
      if x >= 0 && x < m && y >= 0 && y < n && grid[i][j] < grid[x][y] {
        f[i][j] = (f[i][j] + dfs(x, y)) % mod
      }
    }
    return f[i][j]
  }
  for i, row := range grid {
    for j := range row {
      ans = (ans + dfs(i, j)) % mod
    }
  }
  return
}

function countPaths(grid: number[][]): number {
  const mod = 1e9 + 7;
  const m = grid.length;
  const n = grid[0].length;
  const f = new Array(m).fill(0).map(() => new Array(n).fill(0));
  const dfs = (i: number, j: number): number => {
    if (f[i][j]) {
      return f[i][j];
    }
    let ans = 1;
    const dirs: number[] = [-1, 0, 1, 0, -1];
    for (let k = 0; k < 4; ++k) {
      const x = i + dirs[k];
      const y = j + dirs[k + 1];
      if (x >= 0 && x < m && y >= 0 && y < n && grid[i][j] < grid[x][y]) {
        ans = (ans + dfs(x, y)) % mod;
      }
    }
    return (f[i][j] = ans);
  };
  let ans = 0;
  for (let i = 0; i < m; ++i) {
    for (let j = 0; j < n; ++j) {
      ans = (ans + dfs(i, j)) % mod;
    }
  }
  return ans;
}