Number of Increasing Paths in a Grid
Problem
Given an m×n grid of integers, count every strictly increasing path. You may start from any cell and move to an adjacent cell (up, down, left, or right) only when the neighbour's value is strictly greater than the current cell's value. A single cell on its own counts as a path of length one. Because the total can be huge, return it modulo 1,000,000,007.
grid = [[1, 1], [3, 4]]8def count_paths(grid):
MOD = 1000000007
m, n = len(grid), len(grid[0])
memo = [[0] * n for _ in range(m)]
def dfs(r, c):
if memo[r][c]:
return memo[r][c]
total = 1
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] > grid[r][c]:
total += dfs(nr, nc)
memo[r][c] = total % MOD
return memo[r][c]
ans = 0
for r in range(m):
for c in range(n):
ans += dfs(r, c)
return ans % MODfunction countPaths(grid) {
const MOD = 1000000007n;
const m = grid.length, n = grid[0].length;
const memo = Array.from({ length: m }, () => new Array(n).fill(0n));
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
function dfs(r, c) {
if (memo[r][c]) return memo[r][c];
let total = 1n;
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] > grid[r][c]) {
total += dfs(nr, nc);
}
}
memo[r][c] = total % MOD;
return memo[r][c];
}
let ans = 0n;
for (let r = 0; r < m; r++)
for (let c = 0; c < n; c++) ans += dfs(r, c);
return Number(ans % MOD);
}class Solution {
static final int MOD = 1000000007;
int m, n;
int[][] grid, memo;
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public int countPaths(int[][] grid) {
this.grid = grid;
m = grid.length; n = grid[0].length;
memo = new int[m][n];
long ans = 0;
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++) ans += dfs(r, c);
return (int) (ans % MOD);
}
int dfs(int r, int c) {
if (memo[r][c] != 0) return memo[r][c];
long total = 1;
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] > grid[r][c])
total += dfs(nr, nc);
}
return memo[r][c] = (int) (total % MOD);
}
}int countPaths(vector<vector<int>>& grid) {
const int MOD = 1000000007;
int m = grid.size(), n = grid[0].size();
vector<vector<int>> memo(m, vector<int>(n, 0));
int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
function<long long(int, int)> dfs = [&](int r, int c) -> long long {
if (memo[r][c]) return memo[r][c];
long long total = 1;
for (auto& d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] > grid[r][c])
total += dfs(nr, nc);
}
return memo[r][c] = total % MOD;
};
long long ans = 0;
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++) ans += dfs(r, c);
return (int) (ans % MOD);
}Explanation
A naive idea is to enumerate every strictly increasing path from scratch. But many paths share the same tail, so we would redo the same work over and over. The fix is to define one clear quantity per cell and reuse it.
Let dfs(r, c) be the number of strictly increasing paths that start at cell (r, c). Every such path is at least the single cell itself, so we begin the count at 1. Then for each of the four neighbours whose value is strictly greater, every increasing path starting there can be prefixed with our cell, so we add dfs(neighbour).
Because we only ever step to a strictly larger value, the search can never revisit a cell within one path — there are no cycles to worry about. That also means a memo table is safe: once dfs(r, c) is computed it never changes, so we store it and return the cached value on later visits.
The final answer is the sum of dfs(r, c) over every cell, taken modulo 1,000,000,007.
Trace grid = [[1, 1], [3, 4]]. The 4 (bottom-right) has no larger neighbour, so dfs = 1. The 3 can step to 4, giving 1 + 1 = 2. The top-right 1 can step down to 4, giving 1 + 1 = 2. The top-left 1 can step down to 3 (which is 2), giving 1 + 2 = 3. Summing 3 + 2 + 2 + 1 = 8.