Number of Increasing Paths in a Grid

PHOTO EMBED

Mon Jun 19 2023 03:26:01 GMT+0000 (Coordinated Universal Time)

Saved by @DxBros #c++ #dynamic_programming #increasing_paths_grid

class Solution {
public:
    const int mod = 1e9 + 7;
    int m, n;
    vector<int> dx{1,0,0,-1},dy{0,1,-1,0};
    bool isValid(int x, int y){
        return x >= 0 and x < m and y >= 0 and y < n;
    }
    int dfs(int x, int y, vector<vector<int>>& grid, vector<vector<int>>& dp){
        if(dp[x][y] != -1)
            return dp[x][y];
        int ans = 1;
        for(int i = 0; i < 4; i++){
            int x_ = x + dx[i], y_ = y + dy[i];
            if(isValid(x_, y_) and grid[x_][y_] >grid[x][y])
                ans = (ans%mod + dfs(x_,y_,grid, dp)%mod)%mod;
        }
        return dp[x][y] = ans;
    }
    int countPaths(vector<vector<int>>& grid) {
        m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m + 1, vector<int> ( n + 1, -1));
        int ans = 0;
        for(int i = 0; i < m; i++)
            for(int j = 0;j <n ;j++)
                ans = (ans%mod + dfs(i, j,grid, dp));
        return ans;
    }
};
content_copyCOPY

https://leetcode.com/problems/number-of-increasing-paths-in-a-grid/submissions/