leetcode-6110：网格图中递增路径的数目

题目

题目连接

给你一个 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 。

解题

方法一：dfs记忆化搜索

通过memory数组保存，每个格点的递增路径数目
比如memory[i][j],表示终点为(i,j)的递增路径数目

class Solution {
    
public:
    const int MOD=1e9+7;
    vector<vector<int>> dirs={
    {
    -1,0},{
    0,-1},{
    1,0},{
    0,1}};
    vector<vector<int>> memory;
    int dfs(vector<vector<int>>& grid,int i,int j){
    
        if(memory[i][j]>0) return memory[i][j];
        memory[i][j]=1;
        for(vector<int>& dir:dirs){
    
            int nx=i+dir[0];
            int ny=j+dir[1];
            if(nx<0||nx>=grid.size()||ny<0||ny>=grid[0].size()||grid[i][j]<=grid[nx][ny]) continue;
            memory[i][j]=(memory[i][j]+dfs(grid,nx,ny))%MOD;
        }
        return memory[i][j];

     }
    int countPaths(vector<vector<int>>& grid) {
    
        int m=grid.size();
        int n=grid[0].size();
        memory.resize(m,vector<int>(n));
        int res=0;
        for(int i=0;i<m;i++){
    
            for(int j=0;j<n;j++){
    
                res=(res+dfs(grid,i,j))%MOD;
            }
        }
        return res;
    }
};

方法二：动态规划（超时）

dp[i][j][l]表示格点为(i,j)，路径长度为l的数量，
这样做的目的是因为，只有得到长度为 l-1的路径数量，才能计算出长度为l的路径数量。
缺点：
然而比如 grid[2][3]>grid[2][4]
但是每次都会进行重复比较，遍历到(2,3)，会跟右边比，遍历到(2,4)还要跟左边比，并且没法记忆化，因为dp[i][j][l]只是l长度的结果，只是一个中间值，不是最终结果。

而方法一：是直接保存了每个格点的所有递增路径数目，因此可以记忆化。（dfs，复杂度$O(n^2)$）
方法二可以得到每种路径长度的数量，小量数据可以通过，但是会超时。（矩阵遍历，复杂度$O(n^3)$）

class Solution {
    
public:
    const int Mod=1e9+7;
    vector<vector<int>> dirs={
    {
    -1,0},{
    0,-1},{
    1,0},{
    0,1}};
    int countPaths(vector<vector<int>>& grid) {
    
        int res=0;
        int m=grid.size();
        int n=grid[0].size();
        int maxPath=m*n;
        vector<vector<vector<int>>> dp(m,vector<vector<int>>(n,vector<int>(m*n+1)));
        for(int i=0;i<m;i++){
    
            for(int j=0;j<n;j++){
    
                dp[i][j][0]=0;
                dp[i][j][1]=1;
                res++;
            }
        }
        for(int l=2;l<=maxPath;l++){
    
            for(int i=0;i<m;i++){
    
                for(int j=0;j<n;j++){
    
                    dp[i][j][l]=0;
                    for(vector<int>& dir:dirs){
    
                        int nx=i+dir[0];
                        int ny=j+dir[1];
                        if(nx>=0&&nx<m&&ny>=0&&ny<n&&grid[i][j]>grid[nx][ny]){
    
                            dp[i][j][l]+=dp[nx][ny][l-1];
                        }
                    }
                    res=(res+dp[i][j][l])%Mod;
                }
            }
            
        }
        return res;
    }
};