2328. 网格图中递增路径的数目(记忆化搜索)

2328. 网格图中递增路径的数目(记忆化搜索)

原理矩阵的四周扩散，也可以记忆化dp。

时间复杂度：$O(nm)$

class Solution {
    
public:
    int countPaths(vector<vector<int>>& a) {
    
        int n =a.size(),m=a[0].size();
        vector<vector<int> >f(n,vector<int>(m,-1));
        int d[4][2] ={
    0,1,0,-1,1,0,-1,0};
        const int mod = 1e9+7;
        function<int(int,int)> dfs = [&](int x,int y){
    
            if(~f[x][y]) return f[x][y];
            int ans = 1;
            for(int i=0;i<4;i++){
    
                int nx = x+d[i][0],ny=y+d[i][1];
                if(nx>=0 && nx<n && ny>=0 && ny<m && a[nx][ny] >a[x][y]){
    
                    ans=(ans+dfs(nx,ny))%mod;
                }
            }
            return f[x][y] =ans;
        };
        int ans=0;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++) ans=(ans+dfs(i,j))%mod;
        return ans;
    }
};