Longest Path in a matrix

Given a n*m matrix, find the maximum length path (starting from any cell) such that all cells along the path are in strictly increasing order.

We can move in 4 directions from a given cell (i, j), i.e., we can move to (i+1, j) or (i, j+1) or (i-1, j) or (i, j-1).

• Time : O(nm)
• Space : O(nm)

class Solution {
    vector<vector<int>> dp;
    int n, m;
    int dy[4]{-1,0,1,0}, dx[4]{0,1,0,-1};
    int dfs(vector<vector<int>>& matrix, int y, int x) {
        if(dp[y][x] != -1) return dp[y][x];
        dp[y][x] = 1;
        for(int i = 0; i < 4; i++) {
            int ny = y + dy[i], nx = x + dx[i];
            if(0 <= ny and ny < n and 0 <= nx and nx < m and matrix[ny][nx] < matrix[y][x]) {
                dp[y][x] = max(dp[y][x], 1 + dfs(matrix, ny, nx));
            }
        }
        return dp[y][x];
    }
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        n = matrix.size(), m = matrix[0].size();
        dp = vector<vector<int>>(n, vector<int>(m, -1));
        int res = 0;
        
        for(int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                res = max(res, dfs(matrix, i, j));
            }
        }
        
        return res;
    }
};