What is the key pattern in Number of Increasing Paths in a Grid?

The core pattern is graph indegree plus topological ordering. Strictly increasing moves guarantee a DAG, so you can process cells from smaller layers to larger layers and accumulate path counts without cycles.

Why does each cell start with a DP value of 1?

A single cell is already a valid strictly increasing path of length one. That base contribution is necessary before extending paths into larger neighbors, otherwise every answer will be short by the number of cells.

Can I solve this problem with DFS and memoization instead?

Yes. Memoized DFS is a standard alternative where each state returns the number of increasing paths starting from that cell. The topological approach is often easier to reason about iteratively when you want explicit DAG processing.

Why are equal neighboring values ignored?

The problem requires strictly increasing paths, so moving from a value to the same value is illegal. Ignoring equal-value neighbors is what preserves the DAG property and prevents invalid transitions.

What makes this problem hard instead of a basic grid DP?

The difficulty comes from overlapping path suffixes across many start cells and from the fact that movement is not limited to a fixed direction like right or down. You need to exploit the value-based ordering of the grid, not the row and column layout alone.

#2328

Hard

auto_awesome动态·规划

LeetCode 题解工作台

网格图中递增路径的数目

给你一个 m x n 的整数网格图 grid ，你可以从一个格子移动到 4 个方向相邻的任意一个格子。请你返回在网格图中从任意格子出发，达到任意格子，且路径中的数字是严格递增的路径数目。由于答案可能会很大，请将结果对 10 9 + 7 取余后返回。如果两条路径中访问过的格子不是完全…

数组动态规划深度优先搜索广度优先搜索图

题目描述

给你一个 m x n 的整数网格图 grid ，你可以从一个格子移动到 4 个方向相邻的任意一个格子。

请你返回在网格图中从任意格子出发，达到任意格子，且路径中的数字是 严格递增 的路径数目。由于答案可能会很大，请将结果对 10⁹ + 7 取余后返回。

如果两条路径中访问过的格子不是完全相同的，那么它们视为两条不同的路径。

示例 1：

输入：grid = [[1,1],[3,4]]
输出：8
解释：严格递增路径包括：
- 长度为 1 的路径：[1]，[1]，[3]，[4] 。
- 长度为 2 的路径：[1 -> 3]，[1 -> 4]，[3 -> 4] 。
- 长度为 3 的路径：[1 -> 3 -> 4] 。
路径数目为 4 + 3 + 1 = 8 。

示例 2：

输入：grid = [[1],[2]]
输出：3
解释：严格递增路径包括：
- 长度为 1 的路径：[1]，[2] 。
- 长度为 2 的路径：[1 -> 2] 。
路径数目为 2 + 1 = 3 。

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 1000
1 <= m * n <= 10⁵
1 <= grid[i][j] <= 10⁵

lightbulb

解题思路

方法一：记忆化搜索

我们设计一个函数 $dfs(i, j)$ ，表示从网格图中的第 $i$ 行第 $j$ 列的格子出发，能够到达任意格子的严格递增路径数目。那么答案就是 $\sum_{i=0}^{m-1} \sum_{j=0}^{n-1} dfs(i, j)$ 。搜索过程中，我们可以用一个二维数组 $f$ 记录已经计算过的结果，避免重复计算。

函数 $dfs(i, j)$ 的计算过程如下：

如果 $f[i][j]$ 不为 $0$ ，说明已经计算过，直接返回 $f[i][j]$ ；
否则，我们初始化 $f[i][j] = 1$ ，然后枚举 $(i, j)$ 的四个方向，如果某个方向的格子 $(x, y)$ 满足 $0 \leq x \lt m$ , $0 \leq y \lt n$ 且 $grid[i][j] \lt grid[x][y]$ ，我们就可以从格子 $(i, j)$ 出发，到达格子 $(x, y)$ ，且路径上的数字是严格递增的，因此有 $f[i][j] += dfs(x, y)$ 。

最后，我们返回 $f[i][j]$ 。

答案为 $\sum_{i=0}^{m-1} \sum_{j=0}^{n-1} dfs(i, j)$ 。

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 和 $n$ 分别是网格图的行数和列数。

相似题目：

329. 矩阵中的最长递增路径。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
They want you to notice the grid forms a DAG because values must strictly increase on every move.
question_mark
A strong answer explains why each cell starts with one path before extending counts to larger neighbors.
question_mark
If you mention both memoized DFS and indegree topological DP, then justify why the graph ordering is clean here, that is usually a positive signal.

warning

常见陷阱

外企场景

error
Forgetting that every single cell counts as its own increasing path, which undercounts examples like [[1],[2]].
error
Adding edges between equal values or using non-strict comparisons, which creates invalid transitions for this exact problem.
error
Applying modulo only at the very end, which risks overflow and makes intermediate DP updates incorrect in large grids.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Solve the same grid by memoized DFS where dp[i][j] stores the number of increasing paths starting at cell (i, j).
arrow_right_alt
Count decreasing paths instead by reversing the comparison direction or flipping edge construction.
arrow_right_alt
Return the longest increasing path length instead of the total count, which changes the DP transition from summation to maximization.

help

常见问题

外企场景

继续练习

#329 矩阵中的最长递增路径 #1728 猫和老鼠 II #2556 二进制矩阵中翻转最多一次使路径不连通