2328. Number of Increasing Paths in a Grid

• Time: $O(mn)$
• Space: $O(mn)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 class Solution { public: int countPaths(vector>& grid) { m = grid.size(); n = grid[0].size(); int ans = 0; // dp[i][j] := # of increasing paths starting from (i, j) dp.resize(m, vector(n, -1)); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) { ans += dfs(grid, i, j); ans %= kMod; } return ans; } private: static constexpr int kMod = 1'000'000'007; const vector dirs{0, 1, 0, -1, 0}; int m; int n; vector> dp; int dfs(const vector>& grid, int i, int j) { if (dp[i][j] != -1) return dp[i][j]; dp[i][j] = 1; // Current cell contributes 1 length for (int k = 0; k < 4; ++k) { const int x = i + dirs[k]; const int y = j + dirs[k + 1]; if (x < 0 || x == m || y < 0 || y == n) continue; if (grid[x][y] <= grid[i][j]) continue; dp[i][j] += dfs(grid, x, y); dp[i][j] %= kMod; } return dp[i][j]; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 class Solution { public int countPaths(int[][] grid) { m = grid.length; n = grid[0].length; int ans = 0; // dp[i][j] := # of increasing paths starting from (i, j) dp = new int[m][n]; Arrays.stream(dp).forEach(A -> Arrays.fill(A, -1)); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) { ans += dfs(grid, i, j); ans %= kMod; } return ans; } private static final int kMod = 1_000_000_007; private final int[] dirs = {0, 1, 0, -1, 0}; private int m; private int n; private int[][] dp; private int dfs(int[][] grid, int i, int j) { if (dp[i][j] != -1) return dp[i][j]; dp[i][j] = 1; // Current cell contributes 1 length for (int k = 0; k < 4; ++k) { final int x = i + dirs[k]; final int y = j + dirs[k + 1]; if (x < 0 || x == m || y < 0 || y == n) continue; if (grid[x][y] <= grid[i][j]) continue; dp[i][j] += dfs(grid, x, y); dp[i][j] %= kMod; } return dp[i][j]; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution: def countPaths(self, grid: List[List[int]]) -> int: kMod = 1_000_000_007 m = len(grid) n = len(grid[0]) dirs = [0, 1, 0, -1, 0] # dp(i, j) := # of increasing paths starting from (i, j) @functools.lru_cache(None) def dp(i: int, j: int) -> int: ans = 1 # Current cell contributes 1 length for k in range(4): x = i + dirs[k] y = j + dirs[k + 1] if x < 0 or x == m or y < 0 or y == n: continue if grid[x][y] <= grid[i][j]: continue ans += dp(x, y) ans %= kMod return ans return sum(dp(i, j) for i in range(m) for j in range(n)) % kMod