Thinking process

loop through each element in the matrix and set them as the root to do dfs

use another matrix to cache

Mistakes

cache might be overwritten by smaller path length, so use Math.max

public class Solution {
    private int longestPathLength;
    private int[] dx = {-1, 0, 1, 0};
    private int[] dy = {0, 1, 0, -1};

    public int longestIncreasingPath(int[][] matrix) {
        longestPathLength = 0;
        //validate input
        if (matrix == null || matrix.length == 0) return longestPathLength;

        int n = matrix.length, m = matrix[0].length;
        int[][] cache = new int[n][m];
        boolean[][] visited = new boolean[n][m];
        //loop
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                //dfs
                dfsHelper(matrix, cache, visited, i, j);
            }
        }

        //return
        return longestPathLength;
    }

    private void dfsHelper(int[][] matrix, int[][] cache, boolean[][] visited, int x, int y) {
        //exit


        for (int i = 0; i < dx.length; ++i) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (xx >= 0 && xx < matrix.length && yy >= 0 && yy < matrix[0].length && !visited[xx][yy]) {
                //cache? larger?
                if (cache[xx][yy] > 0 && matrix[xx][yy] > matrix[x][y]) {
                    cache[x][y] = Math.max(cache[xx][yy] + 1, cache[x][y]);
                } else if (matrix[xx][yy] > matrix[x][y]){
                    visited[x][y] = true;
                    dfsHelper(matrix, cache, visited, xx, yy);
                    cache[x][y] = Math.max(cache[xx][yy] + 1, cache[x][y]);
                    visited[x][y] = false;
                }
            }
        }

        if (cache[x][y] == 0) {
            cache[x][y] = 1;
        }

        longestPathLength = Math.max(longestPathLength, cache[x][y]);
    }
}

Improve - no global variable

public class Solution {
    private int[] dx = {-1, 0, 1, 0};
    private int[] dy = {0, 1, 0, -1};

    public int longestIncreasingPath(int[][] matrix) {
        //validate input
        if (matrix == null || matrix.length == 0) return 0;

        int n = matrix.length, m = matrix[0].length;
        int[][] cache = new int[n][m];
        boolean[][] visited = new boolean[n][m];

        int longestPathLength = 1;
        //loop
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                //dfs
                int tmpLen = dfsHelper(matrix, cache, visited, i, j);
                longestPathLength = Math.max(longestPathLength, tmpLen);
            }
        }

        //return
        return longestPathLength;
    }

    private int dfsHelper(int[][] matrix, int[][] cache, boolean[][] visited, int x, int y) {
        if (cache[x][y] != 0) return cache[x][y];

        for (int i = 0; i < dx.length; ++i) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (xx >= 0 && xx < matrix.length && yy >= 0 && yy < matrix[0].length && !visited[xx][yy]) {
               if (matrix[xx][yy] > matrix[x][y]){
                    visited[x][y] = true;
                    int tmpLen = dfsHelper(matrix, cache, visited, xx, yy);
                    cache[x][y] = Math.max(tmpLen + 1, cache[x][y]);
                    visited[x][y] = false;
                }
            }
        }

        if (cache[x][y] == 0) {
            cache[x][y] = 1;
        }

        return cache[x][y];
    }
}

Improve - get rid of visited matrix

no need for a visited matrix, cause it won't go to a node twice since we have matrix[][] > matrix[][] and cache

public class Solution {
    private int[] dx = {-1, 0, 1, 0};
    private int[] dy = {0, 1, 0, -1};

    public int longestIncreasingPath(int[][] matrix) {
        //validate input
        if (matrix == null || matrix.length == 0) return 0;

        int n = matrix.length, m = matrix[0].length;
        int[][] cache = new int[n][m];

        int longestPathLength = 1;
        //loop
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                //dfs
                int tmpLen = dfsHelper(matrix, cache, i, j);
                longestPathLength = Math.max(longestPathLength, tmpLen);
            }
        }

        //return
        return longestPathLength;
    }

    private int dfsHelper(int[][] matrix, int[][] cache, int x, int y) {
        if (cache[x][y] != 0) return cache[x][y];

        for (int i = 0; i < dx.length; ++i) {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if (xx >= 0 && xx < matrix.length && yy >= 0 && yy < matrix[0].length) {
               if (matrix[xx][yy] > matrix[x][y]){
                    int tmpLen = dfsHelper(matrix, cache, xx, yy);
                    cache[x][y] = Math.max(tmpLen + 1, cache[x][y]);
                }
            }
        }

        if (cache[x][y] == 0) {
            cache[x][y] = 1;
        }

        return cache[x][y];
    }
}