number-of-increasing-paths-in-a-grid

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an <code>m x n</code> integer matrix <code>grid</code>, where you can move from a cell to any adjacent cell in all <code>4</code> directions.

Return the number of strictly increasing paths in the grid such that you can start from any cell and end at any cell. Since the answer may be very large, return it modulo <code>109 + 7</code>.

Two paths are considered different if they do not have exactly the same sequence of visited cells.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2022/05/10/griddrawio-4.png" style="width: 181px; height: 121px;" />
<pre>
Input: grid = [[1,1],[3,4]]
Output: 8
Explanation: The strictly increasing paths are:
- Paths with length 1: [1], [1], [3], [4].
- Paths with length 2: [1 -&gt; 3], [1 -&gt; 4], [3 -&gt; 4].
- Paths with length 3: [1 -&gt; 3 -&gt; 4].
The total number of paths is 4 + 3 + 1 = 8.
</pre>

Example 2:

<pre>
Input: grid = [[1],[2]]
Output: 3
Explanation: The strictly increasing paths are:
- Paths with length 1: [1], [2].
- Paths with length 2: [1 -&gt; 2].
The total number of paths is 2 + 1 = 3.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 1000</code></li>
	<li><code>1 &lt;= m * n &lt;= 105</code></li>
	<li><code>1 &lt;= grid[i][j] &lt;= 105</code></li>
</ul>

countPaths

Number of Increasing Paths in a Grid

Longest Increasing Path in a Matrix

longest-increasing-path-in-a-matrix

矩阵中的最长递增路径

All Paths From Source to Target

all-paths-from-source-to-target

所有可能的路径

Maximum Strictly Increasing Cells in a Matrix

maximum-strictly-increasing-cells-in-a-matrix

矩阵中严格递增的单元格数

Depth-First Search

Breadth-First Search

Graph

Topological Sort

Memoization

Array

Dynamic Programming

Matrix

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

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

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

&nbsp;

示例 1：

<img alt="" src="https://assets.leetcode.com/uploads/2022/05/10/griddrawio-4.png" style="width: 181px; height: 121px;">

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

示例 2：

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

&nbsp;

提示：

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 1000</code></li>
	<li><code>1 &lt;= m * n &lt;= 105</code></li>
	<li><code>1 &lt;= grid[i][j] &lt;= 105</code></li>
</ul>