Hard

题目描述

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

请你返回在网格中从任意格子出发，达到任意格子，且路径中的数字是严格递增的路径数目。由于答案可能会很大，请将结果对 10^9 + 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^5
  • 1 <= grid[i][j] <= 10^5

解题思路

这道题要求计算网格中所有严格递增路径的数目，可以使用动态规划结合记忆化搜索来解决。

核心思路：

定义 dp[i][j] 为从位置 (i,j) 开始的严格递增路径数目。对于每个位置，我们可以向四个相邻方向探索，如果相邻位置的值更大，就可以扩展路径。

算法流程：

  1. 使用DFS + 记忆化搜索，对每个位置 (i,j) 计算从该位置出发的递增路径数
  2. 状态转移方程：dp[i][j] = 1 + sum(dp[ni][nj]) ，其中 (ni,nj) 是相邻且值更大的位置
  3. 基础情况：每个位置至少有一条路径（自己本身）
  4. 最终答案是所有位置的路径数之和

优化要点：

  • 使用记忆化避免重复计算
  • 由于路径必须严格递增，不会形成环路，DFS是安全的
  • 每个位置只需要计算一次，时间复杂度为 O(mn)

这种方法比暴力枚举所有路径要高效得多，通过记忆化将指数级的时间复杂度降低到线性级别。

代码实现

class Solution {
public:
    int countPaths(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        const int MOD = 1e9 + 7;
        vector<vector<int>> dp(m, vector<int>(n, -1));
        int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        function<int(int, int)> dfs = [&](int i, int j) -> int {
            if (dp[i][j] != -1) return dp[i][j];
            
            dp[i][j] = 1;  // 至少包含自己这一个位置的路径
            
            for (auto& dir : directions) {
                int ni = i + dir[0], nj = j + dir[1];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] > grid[i][j]) {
                    dp[i][j] = (dp[i][j] + dfs(ni, nj)) % MOD;
                }
            }
            
            return dp[i][j];
        };
        
        int result = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                result = (result + dfs(i, j)) % MOD;
            }
        }
        
        return result;
    }
};

class Solution:
    def countPaths(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        MOD = 10**9 + 7
        dp = {}
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        
        def dfs(i, j):
            if (i, j) in dp:
                return dp[(i, j)]
            
            dp[(i, j)] = 1  # 至少包含自己这一个位置的路径
            
            for di, dj in directions:
                ni, nj = i + di, j + dj
                if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] > grid[i][j]:
                    dp[(i, j)] = (dp[(i, j)] + dfs(ni, nj)) % MOD
            
            return dp[(i, j)]
        
        result = 0
        for i in range(m):
            for j in range(n):
                result = (result + dfs(i, j)) % MOD
        
        return result

public class Solution {
    private int MOD = 1000000007;
    private int[,] dp;
    private int[][] grid;
    private int m, n;
    private int[,] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    public int CountPaths(int[][] grid) {
        this.grid = grid;
        m = grid.Length;
        n = grid[0].Length;
        dp = new int[m, n];
        
        // 初始化dp数组为-1
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dp[i, j] = -1;
            }
        }
        
        int result = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                result = (result + DFS(i, j)) % MOD;
            }
        }
        
        return result;
    }
    
    private int DFS(int i, int j) {
        if (dp[i, j] != -1) return dp[i, j];
        
        dp[i, j] = 1;  // 至少包含自己这一个位置的路径
        
        for (int d = 0; d < 4; d++) {
            int ni = i + directions[d, 0];
            int nj = j + directions[d, 1];
            if (ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] > grid[i][j]) {
                dp[i, j] = (dp[i, j] + DFS(ni, nj)) % MOD;
            }
        }
        
        return dp[i, j];
    }
}

var countPaths = function(grid) {
    const m = grid.length, n = grid[0].length;
    const MOD = 1e9 + 7;
    const dp = Array(m).fill(null).map(() => Array(n).fill(-1));
    const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    
    const dfs = (i, j) => {
        if (dp[i][j] !== -1) return dp[i][j];
        
        dp[i][j] = 1;  // 至少包含自己这一个位置的路径
        
        for (const [di, dj] of directions) {
            const ni = i + di, nj = j + dj;
            if (ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] > grid[i][j]) {
                dp[i][j] = (dp[i][j] + dfs(ni, nj)) % MOD;
            }
        }
        
        return dp[i][j];
    };
    
    let result = 0;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            result = (result + dfs(i, j)) % MOD;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(mn)每个位置只计算一次，共有mn个位置
空间复杂度O(mn)需要dp数组存储每个位置的结果，递归栈深度最多为mn

相关题目