Number of Increasing Paths in a Grid LeetCode solution in Rust

1
impl Solution {
2
  pub fn count_paths(grid: Vec<Vec<i32>>) -> i32 {
3
    let mut dp = vec![vec![0; grid[0].len()]; grid.len()];
4

5
    let mut count = 0;
6
    for i in 0..grid.len() {
7
      for j in 0..grid[i].len() {
8
        count += search(&grid, i, j, &mut dp);
9
        count %= M;
10
      }
11
    }
12
    return count;
13
  }
14
}
15

16
const M: i32 = 1_000_000_000 + 7;
17

18
fn search(grid: &Vec<Vec<i32>>, i: usize, j: usize, dp: &mut Vec<Vec<i32>>) -> i32 {
19
  let count = dp[i][j];
20
  if count > 0 {
21
    return count;
22
  }
23

24
  let v = grid[i][j];
25

26
  let mut count = 1;
27

28
  if i + 1 != grid.len() && v < grid[i + 1][j] {
29
    count += search(grid, i + 1, j, dp);
30
    count %= M;
31
  }
32
  if j + 1 != grid[i].len() && v < grid[i][j + 1] {
33
    count += search(grid, i, j + 1, dp);
34
    count %= M;
35
  }
36
  if i != 0 && v < grid[i - 1][j] {
37
    count += search(grid, i - 1, j, dp);
38
    count %= M;
39
  }
40
  if j != 0 && v < grid[i][j - 1] {
41
    count += search(grid, i, j - 1, dp);
42
    count %= M;
43
  }
44
  dp[i][j] = count;
45

46
  return count;
47
}