Given an m x n integers matrix, return the length of the longest increasing path in matrix.

From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).

&nbsp;
Example 1:

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].


Example 2:

Input: matrix = [[3,4,5],[3,2,6],[2,2,1]]
Output: 4
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.


Example 3:

Input: matrix = [[1]]
Output: 1


&nbsp;
Constraints:


	m == matrix.length
	n == matrix[i].length
	1 &lt;= m, n &lt;= 200
	0 &lt;= matrix[i][j] &lt;= 231 - 1


class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        ROWS, COLS = len(matrix), len(matrix[0])
        dp = {}
        
        def dfs(r, c, prevVal):
            if (r < 0 or r == ROWS or
                c < 0 or c == COLS or
                matrix[r][c] <= prevVal):
                return 0
            if (r, c) in dp:
                return dp[(r, c)]
            res = 1
            res = max(res, 1 + dfs(r + 1, c, matrix[r][c]))
            res = max(res, 1 + dfs(r - 1, c, matrix[r][c]))
            res = max(res, 1 + dfs(r, c + 1, matrix[r][c]))
            res = max(res, 1 + dfs(r, c - 1, matrix[r][c]))
            dp[(r, c)] = res
            return res
        for r in range(ROWS):
            for c in range(COLS):
                dfs(r, c, -1)
        return max(dp.values())
class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        int[][] memo = new int[matrix.length][matrix[0].length];
        int longestPath = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                dfs(matrix, i, j, memo);
                longestPath = Math.max(longestPath, memo[i][j]);
            }
        }
        return longestPath;
    }

    private void dfs(int[][] matrix, int i, int j, int[][] memo) {
        if (memo[i][j] != 0)
            return;
        int[][] dirs = {{-1,0}, {0,1}, {1,0}, {0,-1}};
        int max = 0;
        for (int k = 0; k < dirs.length; k++) {
            int x = dirs[k][0] + i;
            int y = dirs[k][1] + j;
            if (isValid(matrix, x, y) && matrix[x][y] > matrix[i][j]) {
                // Get/compute the largest path for that index
                if (memo[x][y] == 0) { // If longest path doesn't exist for that path then compute it
                    dfs(matrix, x, y, memo);
                }
                max = Math.max(max, memo[x][y]);
            }
        }
        memo[i][j] = 1 + max;
    }

    private boolean isValid(int[][] matrix, int i, int j) {
        if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length)
            return false;
        return true;
    }
}
class Solution {
public:
    
    // declare a dp
    
    int dp[205][205];
    
    // direction coordinates of left, right, up, down
    
    vector<int> dx = {-1, 0, 1, 0};
    
    vector<int> dy = {0, 1, 0, -1};
    
    // dfs function
    
    int dfs(vector<vector<int>>& matrix, int i, int j, int n, int m)
    {
        // if value is already calculated for (i, j)th cell
        
        if(dp[i][j] != -1)
            return dp[i][j];
        
        // take the maximum of longest increasing path from all four directions
        
        int maxi = 0;
        
        for(int k = 0; k < 4; k++)
        {
            int new_i = i + dx[k];
            
            int new_j = j + dy[k];
            
            if(new_i >= 0 && new_i < n && new_j >= 0 && new_j < m && matrix[new_i][new_j] > matrix[i][j])
            {
                maxi = max(maxi, dfs(matrix, new_i, new_j, n, m));
            }
        }
        
        // store the res and return it
        
        return dp[i][j] = 1 + maxi;
    }
    
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        
        int n = matrix.size();
        
        int m = matrix[0].size();
        
        // initialize dp with -1
        
        memset(dp, -1, sizeof(dp));
        
        // find the longest increasing path for each cell and take maximum of it
        
        int maxi = INT_MIN;
        
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                int ans = dfs(matrix, i, j, n, m);
                
                maxi = max(maxi, ans);
            }
        }
        
        return maxi;
    }
};
var longestIncreasingPath = function(matrix) {
    const m = matrix.length, n = matrix[0].length;
    const dp = new Array(m).fill(0).map(() => {
        return new Array(n).fill(-1);
    });

    let ans = 0;
    const dir = [0, -1, 0, 1, 0];

    const dfs = (x, y) => {
        if(dp[x][y] != -1) return dp[x][y];

        for(let i = 1; i <= 4; i++) {
            const [nx, ny] = [x + dir[i], y + dir[i - 1]];
            if(
                nx >= 0 && ny >= 0 &&
                nx < m && ny < n &&
                matrix[nx][ny] > matrix[x][y]
            ) {
                dp[x][y] = Math.max(dp[x][y], 1 + dfs(nx, ny));
            }
        }

        if(dp[x][y] == -1) dp[x][y] = 1;
        ans = Math.max(ans, dp[x][y]);
        return dp[x][y];
    }

    for(let i = 0; i < m; i++) {
        for(let j = 0; j < n; j++) {
            if(dp[i][j] == -1) dfs(i, j);
        }
    }

    return ans;
};
Longest Increasing Path in a Matrix