原题链接在这里：

Given an integer matrix, find the length of the longest increasing path.

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

Example 1:

nums = [  [9,9,4],  [6,6,8],  [2,1,1]]

 

Return 4

The longest increasing path is [1, 2, 6, 9].

Example 2:

nums = [  [3,4,5],  [3,2,6],  [2,2,1]]

 

Return 4

The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

dp[i][j] 表示 当前i, j 位置能都到的最大距离。

dp[i][j] 是通过 dfs 来选的，初始dp[i][j] 都是0, 终止条件是若是走到了一个不是0的位置，那么直接返回dp[x][y]. 可以避免重复计算. 若是dp[x][y]已经有值，说明这个点4个方向的最大值已经找到, 找到dp[x][y]的路径必定是比matrix[x][y]小的，直接返回dp[x][y] 再加上 1 就是之前位置的最大延展长度了。

若是当前位置是0, 就从上下左右四个方向dfs, 若是过了边界或者新位置matrix[x][j] <= 老位置matrix[i][j], 直接跳过continue.

不然len = 1 + dfs. 取四个方向最大的len作为dp[i][j].

Time Complexity: 对于每一个点都做dfs, dfs O(m*n). 所以一共 O(m*n * m*n) = O(m^2 * n^2).

Space: O(m*n).用了dp array.

AC Java:

1 public class Solution { 2     final int [][] fourD = {
   {-1, 0}, {1,0}, {0,-1}, {0,1}}; 3      4     public int longestIncreasingPath(int[][] matrix) { 5         if(matrix == null || matrix.length == 0 || matrix[0].length == 0){ 6             return 0; 7         } 8         int max = 1; 9         int m = matrix.length;10         int n = matrix[0].length;11         int [][] dp = new int[m][n];12         for(int i = 0; i
     
      =m || y<0 || y>=n || matrix[x][y] <= matrix[i][j]){30                 continue;31             }32             int len = 1 + dfs(matrix, x, y, m, n, dp);33             max = Math.max(max, len);34         }35         dp[i][j] = max;36         return dp[i][j];37     }38 }