虽然生活节奏很差，还在坚持一天至少一题（事实上每天都想多做几题，但发现往往只能保证一题，思考时间很长）。

这题让我想到word search，于是模仿word search写了一个dfs，但是数据多的时候会TLE。

BRUTE FORCE DFS(TLE)

    int maxLen = 1;

    public int longestIncreasingPath(int[][] matrix) {
        int m = matrix.length;
        if (m == 0) return 0;
        int n = matrix[0].length;
        if (n == 0) return 0;
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                dfs(matrix, visited, 1, i, j, Integer.MIN_VALUE);
            }
        return maxLen;
    }

    private void dfs(int[][] matrix, boolean[][] visited, int curLen, int x, int y, int pre) {
        if (x >= matrix.length || x < 0 || y >= matrix[0].length || y < 0) {
            return;
        }
        if (visited[x][y]) {
            return;
        }
        if (matrix[x][y] <= pre) {
            return;
        }
        if (curLen > maxLen) {
            maxLen = curLen;
        }
        visited[x][y] = true;
        dfs(matrix, visited, curLen + 1, x + 1, y, matrix[x][y]);
        dfs(matrix, visited, curLen + 1, x - 1, y, matrix[x][y]);
        dfs(matrix, visited, curLen + 1, x, y + 1, matrix[x][y]);
        dfs(matrix, visited, curLen + 1, x, y - 1, matrix[x][y]);
        visited[x][y] = false;
    }

DFS + CACHE

所以我想是不是需要用DP，看了答案，有人用DP。这个答案没用DP，但是用了DP那种cache的思想：

    public static final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public int longestIncreasingPath(int[][] matrix) {
        if (matrix.length == 0) return 0;
        int m = matrix.length, n = matrix[0].length;
        int[][] cache = new int[m][n];
        int max = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int len = dfs(matrix, i, j, cache);
                max = Math.max(len, max);
            }
        }
        return max;
    }

    public int dfs(int[][] matrix, int i, int j, int[][] maxLenFromHere) {
        if (maxLenFromHere[i][j] != 0)
            return maxLenFromHere[i][j];
        int max = 1;
        for (int[] dir : dirs) {
            int x = i + dir[0], y = j + dir[1];
            if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length || matrix[x][y] <= matrix[i][j]) {
                continue;
            }
            //如果四个方向都不满足，下面两行就不会走
            int len = 1 + dfs(matrix, x, y, maxLenFromHere);
            //这个max让我有些疑惑，max = len不行吗？不行的，因为一直在递归，len不是递增的。
            // 另外，max定义在for外面一层刚好，不需要设置成global的
            max = Math.max(max, len);
        }
        maxLenFromHere[i][j] = max;
        return max;
    }

还有其他解法可以看ref。这题确实应该多做几遍的，对递归理解有帮助。

ref:
https://discuss.leetcode.com/topic/34835/15ms-concise-java-solution
http://www.ustopia.cn/t/52?cache=1497459386#Post241