Number of Increasing Paths in a Grid LeetCode solution in Java

1
class Solution {
2
  long[][] dp;
3
  int mod = 1_000_000_007;
4

5
  public int countPaths(int[][] grid) {
6
    dp = new long[grid.length][grid[0].length];
7
    long sum = 0L;
8
    for (int i = 0; i < grid.length; i++) {
9
      for (int j = 0; j < grid[0].length; j++) {
10
        sum = (sum + dfs(grid, i, j, 0)) % mod;
11
      }
12
    }
13
    return (int) sum;
14
  }
15

16
  long dfs(int[][] grid, int i, int j, int pre) {
17
    if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length) return 0;
18
    if (grid[i][j] <= pre) return 0;
19
    if (dp[i][j] > 0) return dp[i][j];
20
    long a = dfs(grid, i + 1, j, grid[i][j]);
21
    long b = dfs(grid, i, j + 1, grid[i][j]);
22
    long c = dfs(grid, i - 1, j, grid[i][j]);
23
    long d = dfs(grid, i, j - 1, grid[i][j]);
24
    dp[i][j] = (1 + a + b + c + d) % mod;
25
    return dp[i][j];
26
  }
27
}